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 metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00841873
Contributor : Cyril Nicaud <>
Submitted on : Tuesday, July 9, 2013 - 8:56:30 AM
Last modification on : Monday, September 16, 2019 - 11:02:09 AM
Long-term archiving on : Thursday, October 10, 2013 - 4:08:19 AM

File

Factorizations_and_Universal_A...
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

572

Files downloads

254