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

Speaker(s)

Olivier Carton; Sebastian Maneth

Affiliation

University of Paris; University of Bremen

Date

May 25, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---