On the computational complexity of problems related to distinguishability sets

DOI10.1016/j.ic.2017.09.003zbMath1390.68396OpenAlexW2751846635MaRDI QIDQ1706155

Markus Holzer, Sebastian Jakobi

Publication date: 21 March 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.09.003

zbMATH Keywords

computational complexitysynchronizationdeterministic finite automatastate complexitydistinguishability sets

Mathematics Subject Classification ID

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

Related Items (3)

Synchronization of Parikh automata ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Constrained synchronization and commutativity

Cites Work

• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• The method of forced enumeration for nondeterministic automata
• On a complexity hierarchy between L and NL
• The parallel complexity of finite-state automata problems
• Space-bounded reducibility among combinatorial problems
• Synchronizing Automata and the Černý Conjecture
• Nondeterministic Space is Closed under Complementation
• Minimal NFA Problems are Hard
• Distinguishability Operations and Closures

This page was built for publication: On the computational complexity of problems related to distinguishability sets