Reset complexity of ideal languages over a binary alphabet

DOI10.1007/978-3-319-60252-3_21MaRDI QIDQ2401010zbMATH OpenOpenAlexFDO

Authors Marina Maslennikova

Publication date 31 August 2017

Full work available at URL http://hdl.handle.net/10995/102109

zbMATH Keywords

ideal languagePSPACE-completenessreset complexityreset wordsynchronizing automaton

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Cited in

(6)

• Sync-maximal permutation groups equal primitive permutation groups
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Reset complexity of ideal languages over a binary alphabet
• Reset sink complexity of regular ideals
• Completely reachable almost group automata

This page was built for publication: Reset complexity of ideal languages over a binary alphabet

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