P(l)aying for Synchronization

DOI10.1007/978-3-642-31606-7_14zbMath1297.68127arXiv1205.2174OpenAlexW2126105820MaRDI QIDQ2914704

Fedor Fominykh, Mikhail V. Volkov, Pavel Martyugin, F. M. Fominykh

Publication date: 20 September 2012

Published in: International Journal of Foundations of Computer Science, Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitydeterministic finite automatonsynchronizing automatondeterministic weighted automatonsynchronization game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Formal languages and automata (68Q45) Other game-theoretic models (91A40)

Related Items (5)

P(l)aying for Synchronization ⋮ Synchronization of Parikh automata ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Synchronizing Automata over Nested Words

Cites Work

• The road coloring problem
• Synchronizing automata with a letter of deficiency 2
• The Synchronizing Probability Function of an Automaton
• P(l)aying for Synchronization
• Modifying the Upper Bound on the Length of Minimal Synchronizing Word
• Play to Test
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
• The Theory of Definite Automata

This page was built for publication: P(l)aying for Synchronization