On Two Algorithmic Problems about Synchronizing Automata

DOI10.1007/978-3-319-09698-8_6zbMath1405.68163arXiv1312.2226OpenAlexW2963853438MaRDI QIDQ2921974

Mikhail V. Berlinkov

Publication date: 14 October 2014

Published in: Developments in Language Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (12)

Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Careful synchronization of partial deterministic finite automata ⋮ Synchronizing automata with coinciding cycles ⋮ The road problem and homomorphisms of directed graphs ⋮ Unnamed Item ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Černý's conjecture and the road colouring problem ⋮ Computational complexity of problems for deterministic presentations of sofic shifts

This page was built for publication: On Two Algorithmic Problems about Synchronizing Automata