A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata
Tekijät: Frei Fabian, Hromkovic Juraj, Karhumäki Juhani
Kustantaja: IOS PRESS
Julkaisuvuosi: 2020
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Vuosikerta: 175
Numero: 1-4
Aloitussivu: 173
Lopetussivu: 185
Sivujen määrä: 13
ISSN: 0169-2968
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-2020-1952
Tiivistelmä
It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L, the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them.Using the above result, we obtain decision algorithms for many natural problems on powers. For example, it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata.
It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L, the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them.Using the above result, we obtain decision algorithms for many natural problems on powers. For example, it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata.
Turun yliopiston Tutkimustietojärjestelmän portaali