---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '22406'
abstract:
- lang: eng
  text: "It is known that for a uniform morphic sequence \U0001D496 =⟨\U0001D462\U0001D45B⟩∞\r\n\U0001D45B=0
    and an algebraic number \U0001D6FD such that |\U0001D6FD| >1, the number [[\U0001D496]]\U0001D6FD
    :=∑∞\r\n\U0001D45B=0(\U0001D462\U0001D45B/\U0001D6FD\U0001D45B) either lies in
    ℚ⁡(\U0001D6FD) or is transcendental. In this paper, we show a similar rational–transcendental
    dichotomy for sequences defined by irreducible Pisot morphisms on binary alphabets.
    Subject to the Pisot conjecture (an irreducible Pisot morphism has pure discrete
    spectrum), we generalise the latter result to arbitrary finite alphabets. In certain
    cases, we are able to show transcendence of [[\U0001D496]]\U0001D6FD outright.
    In particular, for \U0001D458 ≥2, if \U0001D496 is the k-Bonacci word, then [[\U0001D496]]\U0001D6FD
    is transcendental."
acknowledgement: "We thank the anonymous referee for identifying an error in an earlier\r\nversion
  of the paper. We gratefully acknowledge support from UKRI Frontier Research\r\nGrant
  EP/X033813/1, ERC grant DynAMiCS (101167561) and DFG grant 389792660 as\r\npart
  of TRR 248. J.O. is also affiliated with Keble College, Oxford as an Emmy Network\r\nfellow."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Pavol
  full_name: Kebis, Pavol
  id: 2e0132b3-4e98-11ef-b275-cf7281c2802a
  last_name: Kebis
- first_name: FLORIAN
  full_name: LUCA, FLORIAN
  last_name: LUCA
- first_name: JOEL
  full_name: OUAKNINE, JOEL
  last_name: OUAKNINE
- first_name: ANDREW
  full_name: SCOONES, ANDREW
  last_name: SCOONES
- first_name: JAMES
  full_name: WORRELL, JAMES
  last_name: WORRELL
citation:
  ama: Kebis P, LUCA F, OUAKNINE J, SCOONES A, WORRELL J. Transcendence for Pisot
    morphic words over an algebraic base. <i>Ergodic Theory and Dynamical Systems</i>.
    2026:1-22. doi:<a href="https://doi.org/10.1017/etds.2026.10324">10.1017/etds.2026.10324</a>
  apa: Kebis, P., LUCA, F., OUAKNINE, J., SCOONES, A., &#38; WORRELL, J. (2026). Transcendence
    for Pisot morphic words over an algebraic base. <i>Ergodic Theory and Dynamical
    Systems</i>. Cambridge University Press. <a href="https://doi.org/10.1017/etds.2026.10324">https://doi.org/10.1017/etds.2026.10324</a>
  chicago: Kebis, Pavol, FLORIAN LUCA, JOEL OUAKNINE, ANDREW SCOONES, and JAMES WORRELL.
    “Transcendence for Pisot Morphic Words over an Algebraic Base.” <i>Ergodic Theory
    and Dynamical Systems</i>. Cambridge University Press, 2026. <a href="https://doi.org/10.1017/etds.2026.10324">https://doi.org/10.1017/etds.2026.10324</a>.
  ieee: P. Kebis, F. LUCA, J. OUAKNINE, A. SCOONES, and J. WORRELL, “Transcendence
    for Pisot morphic words over an algebraic base,” <i>Ergodic Theory and Dynamical
    Systems</i>. Cambridge University Press, pp. 1–22, 2026.
  ista: Kebis P, LUCA F, OUAKNINE J, SCOONES A, WORRELL J. 2026. Transcendence for
    Pisot morphic words over an algebraic base. Ergodic Theory and Dynamical Systems.,
    1–22.
  mla: Kebis, Pavol, et al. “Transcendence for Pisot Morphic Words over an Algebraic
    Base.” <i>Ergodic Theory and Dynamical Systems</i>, Cambridge University Press,
    2026, pp. 1–22, doi:<a href="https://doi.org/10.1017/etds.2026.10324">10.1017/etds.2026.10324</a>.
  short: P. Kebis, F. LUCA, J. OUAKNINE, A. SCOONES, J. WORRELL, Ergodic Theory and
    Dynamical Systems (2026) 1–22.
das_tickbox: '0'
date_created: 2026-07-27T05:53:25Z
date_published: 2026-07-10T00:00:00Z
date_updated: 2026-08-03T06:17:50Z
day: '10'
ddc:
- '000'
department:
- _id: ToHe
- _id: GradSch
doi: 10.1017/etds.2026.10324
external_id:
  arxiv:
  - '2405.05279'
fulldoi: https://doi.org/10.1017/etds.2026.10324
has_accepted_license: '1'
keyword:
- balanced-pair algorithm
- Cobham’s conjecture
- k-Bonacci words
- Pisot conjecture
- subspace theorem
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1017/etds.2026.10324
mathsc:
- 11J81
- 37B10
- 11J87
month: '07'
oa: 1
oa_version: Published Version
page: 1-22
publication: Ergodic Theory and Dynamical Systems
publication_identifier:
  eissn:
  - 1469-4417
  issn:
  - 0143-3857
publication_status: epub_ahead
publisher: Cambridge University Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Transcendence for Pisot morphic words over an algebraic base
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_type: closed access
_id: '21516'
abstract:
- lang: eng
  text: The notion of elliptic or ellipsoidal conformal equivalent structure is introduced
    to model rough surface topography by use of convex homogenized shapes. The method
    is based on classical stereological results dealing with the relation between
    the number of intersections of an object with a set of parallel straight lines.
    The approach leads to an algorithm comparing the number of intercepts on both
    sampled surfaces and homogenized shapes selected for modeling. Some applications
    using the comparative values of the parameters of the homogenized structures are
    presented in this paper.
article_processing_charge: No
article_type: original
author:
- first_name: Charles
  full_name: Roques-Carmes, Charles
  id: e2e68fc9-6505-11ef-a541-eb4e72cc3e82
  last_name: Roques-Carmes
- first_name: N.
  full_name: Bodin, N.
  last_name: Bodin
- first_name: G.
  full_name: Monteil, G.
  last_name: Monteil
- first_name: J.F.
  full_name: Quiniou, J.F.
  last_name: Quiniou
citation:
  ama: 'Roques-Carmes C, Bodin N, Monteil G, Quiniou JF. Description of rough surfaces
    using conformal equivalent structure concept: Part 1. Stereological approach.
    <i>Wear</i>. 2001;248(1-2):82-91. doi:<a href="https://doi.org/10.1016/s0043-1648(00)00562-7">10.1016/s0043-1648(00)00562-7</a>'
  apa: 'Roques-Carmes, C., Bodin, N., Monteil, G., &#38; Quiniou, J. F. (2001). Description
    of rough surfaces using conformal equivalent structure concept: Part 1. Stereological
    approach. <i>Wear</i>. Elsevier. <a href="https://doi.org/10.1016/s0043-1648(00)00562-7">https://doi.org/10.1016/s0043-1648(00)00562-7</a>'
  chicago: 'Roques-Carmes, Charles, N. Bodin, G. Monteil, and J.F. Quiniou. “Description
    of Rough Surfaces Using Conformal Equivalent Structure Concept: Part 1. Stereological
    Approach.” <i>Wear</i>. Elsevier, 2001. <a href="https://doi.org/10.1016/s0043-1648(00)00562-7">https://doi.org/10.1016/s0043-1648(00)00562-7</a>.'
  ieee: 'C. Roques-Carmes, N. Bodin, G. Monteil, and J. F. Quiniou, “Description of
    rough surfaces using conformal equivalent structure concept: Part 1. Stereological
    approach,” <i>Wear</i>, vol. 248, no. 1–2. Elsevier, pp. 82–91, 2001.'
  ista: 'Roques-Carmes C, Bodin N, Monteil G, Quiniou JF. 2001. Description of rough
    surfaces using conformal equivalent structure concept: Part 1. Stereological approach.
    Wear. 248(1–2), 82–91.'
  mla: 'Roques-Carmes, Charles, et al. “Description of Rough Surfaces Using Conformal
    Equivalent Structure Concept: Part 1. Stereological Approach.” <i>Wear</i>, vol.
    248, no. 1–2, Elsevier, 2001, pp. 82–91, doi:<a href="https://doi.org/10.1016/s0043-1648(00)00562-7">10.1016/s0043-1648(00)00562-7</a>.'
  short: C. Roques-Carmes, N. Bodin, G. Monteil, J.F. Quiniou, Wear 248 (2001) 82–91.
date_created: 2026-03-30T12:22:47Z
date_published: 2001-03-01T00:00:00Z
date_updated: 2026-04-15T13:21:44Z
day: '01'
ddc:
- '530'
doi: 10.1016/s0043-1648(00)00562-7
extern: '1'
fulldoi: https://doi.org/10.1016/s0043-1648(00)00562-7
intvolume: '       248'
issue: 1-2
keyword:
- Rough surface topography
- Stereology
- Algorithm
- Equivalent structure concept
language:
- iso: eng
month: '03'
oa_version: None
page: 82-91
publication: Wear
publication_identifier:
  eissn:
  - 1873-2577
  issn:
  - 0043-1648
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Description of rough surfaces using conformal equivalent structure concept:
  Part 1. Stereological approach'
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 248
year: '2001'
...
---
_id: '11694'
abstract:
- lang: eng
  text: We consider exploration problems where a robot has to construct a complete
    map of an unknown environment. We assume that the environment is modeled by a
    directed, strongly connected graph. The robot's task is to visit all nodes and
    edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou
    [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990,
    pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by
    Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of
    edges in the graph and d is the minimum number of edges that have to be added
    to make the graph Eulerian.  We give the 1rst subexponential algorithm for this
    exploration problem, which achieves an upper bound of dO(logd)m.  We also show
    a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower
    bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration
    algorithms.
acknowledgement: We thank Prabhakar Raghavan for bringing to our attention the literature
  on the s-t connectivity  problem. We also thank  an anonymous referee for many helpful
  comments which improved the presentation of the paper.
article_processing_charge: No
article_type: original
author:
- first_name: Susanne
  full_name: Albers, Susanne
  last_name: Albers
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Albers S, Henzinger M. Exploring unknown environments. <i>SIAM Journal on Computing</i>.
    2000;29(4):1164-1188. doi:<a href="https://doi.org/10.1137/s009753979732428x">10.1137/s009753979732428x</a>
  apa: 'Albers, S., &#38; Henzinger, M. (2000). Exploring unknown environments. <i>SIAM
    Journal on Computing</i>. El Paso, TX, United States: Society for Industrial and
    Applied Mathematics. <a href="https://doi.org/10.1137/s009753979732428x">https://doi.org/10.1137/s009753979732428x</a>'
  chicago: Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.”
    <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics,
    2000. <a href="https://doi.org/10.1137/s009753979732428x">https://doi.org/10.1137/s009753979732428x</a>.
  ieee: S. Albers and M. Henzinger, “Exploring unknown environments,” <i>SIAM Journal
    on Computing</i>, vol. 29, no. 4. Society for Industrial and Applied Mathematics,
    pp. 1164–1188, 2000.
  ista: Albers S, Henzinger M. 2000. Exploring unknown environments. SIAM Journal
    on Computing. 29(4), 1164–1188.
  mla: Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” <i>SIAM
    Journal on Computing</i>, vol. 29, no. 4, Society for Industrial and Applied Mathematics,
    2000, pp. 1164–88, doi:<a href="https://doi.org/10.1137/s009753979732428x">10.1137/s009753979732428x</a>.
  short: S. Albers, M. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.
conference:
  end_date: 1997-05-06
  location: El Paso, TX, United States
  name: 'STOC97: 29th Annual Symposium on Theory of Computing'
  start_date: 1997-05-04
date_created: 2022-07-29T09:04:36Z
date_published: 2000-07-01T00:00:00Z
date_updated: 2024-11-06T12:09:07Z
day: '01'
doi: 10.1137/s009753979732428x
extern: '1'
fulldoi: https://doi.org/10.1137/s009753979732428x
intvolume: '        29'
issue: '4'
keyword:
- directed graph
- exploration algorithm
language:
- iso: eng
month: '07'
oa_version: None
page: 1164-1188
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Exploring unknown environments
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2000'
...
---
_id: '11680'
abstract:
- lang: eng
  text: 'We present a model for edge updates with restricted randomness in dynamic
    graph algorithms and a general technique for analyzing the expected running time
    of an update operation. This model is able to capture the average case in many
    applications, since (1) it allows restrictions on the set of edges which can be
    used for insertions and (2) the type (insertion or deletion) of each update operation
    is arbitrary, i.e., not random. We use our technique to analyze existing and new
    dynamic algorithms for the following problems: maximum cardinality matching, minimum
    spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex
    connectivity, and bipartiteness. Given a random graph G with m 0 edges and n vertices
    and a sequence of l update operations such that the graph contains m i edges after
    operation i , the expected time for performing the updates for any l is O(llogn+∑li=1n/m−−√i)
    in the case of minimum spanning forests, connectivity, 2-edge connectivity, and
    bipartiteness. The expected time per update operation is O(n) in the case of maximum
    matching. We also give improved bounds for k -edge and k -vertex connectivity.
    Additionally we give an insertions-only algorithm for maximum cardinality matching
    with worst-case O(n) amortized time per insertion.'
acknowledgement: The authors would like to thank Emo Welzl for helpful discussions.
article_processing_charge: No
article_type: original
author:
- first_name: D.
  full_name: Alberts, D.
  last_name: Alberts
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Alberts D, Henzinger M. Average-case analysis of dynamic graph algorithms.
    <i>Algorithmica</i>. 1998;20:31-60. doi:<a href="https://doi.org/10.1007/pl00009186">10.1007/pl00009186</a>
  apa: Alberts, D., &#38; Henzinger, M. (1998). Average-case analysis of dynamic graph
    algorithms. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/pl00009186">https://doi.org/10.1007/pl00009186</a>
  chicago: Alberts, D., and Monika Henzinger. “Average-Case Analysis of Dynamic Graph
    Algorithms.” <i>Algorithmica</i>. Springer Nature, 1998. <a href="https://doi.org/10.1007/pl00009186">https://doi.org/10.1007/pl00009186</a>.
  ieee: D. Alberts and M. Henzinger, “Average-case analysis of dynamic graph algorithms,”
    <i>Algorithmica</i>, vol. 20. Springer Nature, pp. 31–60, 1998.
  ista: Alberts D, Henzinger M. 1998. Average-case analysis of dynamic graph algorithms.
    Algorithmica. 20, 31–60.
  mla: Alberts, D., and Monika Henzinger. “Average-Case Analysis of Dynamic Graph
    Algorithms.” <i>Algorithmica</i>, vol. 20, Springer Nature, 1998, pp. 31–60, doi:<a
    href="https://doi.org/10.1007/pl00009186">10.1007/pl00009186</a>.
  short: D. Alberts, M. Henzinger, Algorithmica 20 (1998) 31–60.
date_created: 2022-07-28T06:50:51Z
date_published: 1998-01-01T00:00:00Z
date_updated: 2024-11-06T12:26:40Z
day: '01'
doi: 10.1007/pl00009186
extern: '1'
fulldoi: https://doi.org/10.1007/pl00009186
intvolume: '        20'
keyword:
- Dynamic graph algorithm
- Average-case analysis
- Minimum spanning forest
- Connectivity
- Bipartiteness
- Maximum matching.
language:
- iso: eng
month: '01'
oa_version: None
page: 31-60
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11928'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Average-case analysis of dynamic graph algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '1998'
...