Search

• < Previous
• 1
• Next >

---

Transfinite Lyndon words

Olivier Carton ; Luc Boasson.

In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words. In&nbsp;[&hellip;]

---

Polishness of some topologies related to word or tree automata

Olivier Finkel ; Olivier Carton ; Dominique Lecomte.

We prove that the B\"uchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular the B\"uchi and the Muller topologies are not Polish in this case.

---

Continuity of Functional Transducers: A Profinite Study of Rational Functions

Michaël Cadilhac ; Olivier Carton ; Charles Paperman.

A word-to-word function is continuous for a class of languages~$\mathcal{V}$ if its inverse maps $\mathcal{V}$_languages to~$\mathcal{V}$. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some&nbsp;[&hellip;]

---

A survey on difference hierarchies of regular languages

Olivier Carton ; Dominique Perrin ; Jean-Éric Pin.

Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages. The first sections describe standard techniques on difference hierarchies, mostly due to Hausdorff. We&nbsp;[&hellip;]

---

Deterministic pushdown automata can compress some normal sequences

Olivier Carton ; Sylvain Perifel.

In this paper, we give a deterministic pushdown transducer and a normal sequence of digits compressed by it. This solves positively a question left open in a previous paper by V. Becher, P. A. Heiber and the first author.

---