Reset Complexity of Ideal Languages Over a Binary Alphabet

DOI10.1142/S0129054119400343zbMath1427.68150OpenAlexW2621293383MaRDI QIDQ5205048

Marina Maslennikova

Publication date: 10 December 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054119400343

zbMATH Keywords

state complexityPSPACE-completenessreset wordsynchronizing automatonideal languagereset complexity

Mathematics Subject Classification ID

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

Related Items (8)

Completely distinguishable automata and the set of synchronizing words ⋮ Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ 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 ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Reset complexity and completely reachable automata with simple idempotents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Černý conjecture and 1-contracting automata
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Reset complexity of ideal languages over a binary alphabet
• Completely Reachable Automata
• Synchronizing Automata with Extremal Properties
• Synchronizing Automata and the Černý Conjecture
• Slowly Synchronizing Automata and Digraphs
• Complexity of Checking Whether Two Automata Are Synchronized by the Same Language
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

This page was built for publication: Reset Complexity of Ideal Languages Over a Binary Alphabet