Tight links between normality and automata; Two Applications of the Parikh Property

Prelegent(ci)

Olivier Carton; Sebastian Maneth

Afiliacja

University of Paris; University of Bremen

Termin

25 maja 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

Abstract (Tight links between normality and automata): Normality has been introduced by É. Borel more than one hundred years ago. A real number is normal to an integer base if, in its infinite expansion expressed in that base, all blocks of digits of the same length have the same limiting frequency. Normality formalizes the least requirements about a random sequence. In this talk, we explain several links between this notion and finite-state machines. This includes the characterization of normality by non-compressibility, preservation of normality by selection and computing frequencies with weighted automata. Abstract (Two Applications of the Parikh Property): A language has the Parikh property if, when ignoring the order of letters within a word, the language is equivalent to a regular language. We show the decidability of the equivalence problem for deterministic MSO definable graph-to-string (and graph-to-tree) translations on a context-free set of input graphs. This is achieved by making use of the Parikh property of ranges of such MSO translations and the well known closure and decidability properties of semi-linear sets. In a similar way, but with an even simpler proof, we show that well-brackedness of the ranges of such MSO translations (for a single pair of brackets) is decidable.

---