Principal ideal languages and synchronizing automata

DOI10.3233/FI-2014-1034MaRDI QIDQ2934876zbMATHOpenAlexFDO

Authors Marina Maslennikova, Elena Pribavkina, Vladimir V. Gusev

Publication date 22 December 2014

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3307

zbMATH Keywords

synchronizing wordstrongly connected automatonsyntactic complexitysynchronizing automatonideal language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language.

Recommendations

• Finitely generated ideal languages and synchronizing automata
• Trim Strongly Connected Synchronizing Automata and Ideal Languages
• Representation of (left) ideal regular languages by synchronizing automata
• Regular ideal languages and synchronizing automata
• Strongly connected synchronizing automata and the language of minimal reset words

Cited in

(6)

• On the length of uncompletable words in unambiguous automata
• Trim Strongly Connected Synchronizing Automata and Ideal Languages
• Finitely generated ideal languages and synchronizing automata
• Representation of (left) ideal regular languages by synchronizing automata
• Ideal regular languages and strongly connected synchronizing automata
• Strongly connected synchronizing automata and the language of minimal reset words

This page was built for publication: Principal ideal languages and synchronizing automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934876)