Principal ideal languages and synchronizing automata

DOI10.3233/FI-2014-1034zbMATH Open1302.68162arXiv1304.3307OpenAlexW1807511501MaRDI QIDQ2934876FDOQ2934876

Authors: Marina Maslennikova, Elena Pribavkina, Vladimir V. Gusev 

Publication date: 22 December 2014

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

synchronizing wordstrongly connected automatonsyntactic complexitysynchronizing automatonideal language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (5)

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

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)