Skip to Main content Skip to Navigation
Conference papers

Factorizations and Universal Automaton of Omega Languages

Abstract : In this paper, we extend the concept of factorization on finite words to ω-rational languages and show how to compute them. We define a normal form for Büchi automata and introduce a universal automaton for Büchi automata in normal form. We prove that, for every ω-rational language, this Büchi automaton, based on factorization, is canonical and that it is the smallest automaton that contains the morphic image of every equivalent Büchi automaton in normal form.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Cyril Nicaud Connect in order to contact the contributor
Submitted on : Tuesday, July 9, 2013 - 8:56:30 AM
Last modification on : Saturday, June 25, 2022 - 10:33:43 AM
Long-term archiving on: : Thursday, October 10, 2013 - 4:08:19 AM


Files produced by the author(s)



Vincent Carnino, Sylvain Lombardy. Factorizations and Universal Automaton of Omega Languages. Developments in Language Theory - 17th International Conference (DLT'13), 2013, Marne-la-Vallée, France. pp.338-349, ⟨10.1007/978-3-642-38771-5_30⟩. ⟨hal-00841873⟩



Record views


Files downloads