Synchronizing Automata over Nested Words

DOI10.1007/978-3-662-49630-5_15zbMath1475.68148OpenAlexW2466376928MaRDI QIDQ2811343

Pavel Martyugin, Mahsa Shirmohammadi, Dmitry Chistikov

Publication date: 10 June 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10995/102274

Mathematics Subject Classification ID

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

Related Items (1)

The complexity of synchronizing Markov decision processes

Uses Software

• OpenNWA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The space complexity of pebble games on trees
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Polynomial complete problems in automata theory
• Parikh's theorem: a simple and direct automaton construction
• P(l)aying for Synchronization
• On programming of arithmetic operations
• Adding nesting structure to words
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The Complexity of Finding Reset Words in Finite Automata
• Synchronization of Pushdown Automata
• On two Combinatorial Problems Arising from Automata Theory
• On Time Versus Space
• Hardness Results for Intersection Non-Emptiness
• A Brief History of Strahler Numbers

This page was built for publication: Synchronizing Automata over Nested Words