Complexity of problems concerning reset words for cyclic and Eulerian automata

DOI10.1016/j.tcs.2012.04.022zbMath1279.68163OpenAlexW2175473110MaRDI QIDQ442134

Pavel Martyugin

Publication date: 9 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.022

zbMATH Keywords

computational complexityautomatasynchronizationreset words

Mathematics Subject Classification ID

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

Related Items (5)

Approximating the minimum length of synchronizing words is hard ⋮ Unnamed Item ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Synchronizing monotonic automata
• Synchronizing automata preserving a chain of partial orders
• Synchronizing finite automata on Eulerian digraphs.
• Approximating the minimum length of synchronizing words is hard
• Composition sequences for functions over a finite domain.
• Reset Sequences for Monotonic Automata
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory

This page was built for publication: Complexity of problems concerning reset words for cyclic and Eulerian automata