Synchronizing Automata over Nested Words
From MaRDI portal
Publication:2811343
DOI10.1007/978-3-662-49630-5_15zbMATH Open1475.68148OpenAlexW2466376928MaRDI QIDQ2811343FDOQ2811343
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Synchronizing Automata and the Černý Conjecture
- On programming of arithmetic operations
- Adding nesting structure to words
- Polynomial complete problems in automata theory
- Reset Sequences for Monotonic Automata
- On two Combinatorial Problems Arising from Automata Theory
- On Time Versus Space
- The Complexity of Finding Reset Words in Finite Automata
- Parikh's theorem: a simple and direct automaton construction
- Title not available (Why is that?)
- Synchronization of Pushdown Automata
- Title not available (Why is that?)
- P(l)aying for Synchronization
- Title not available (Why is that?)
- 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
- Hardness Results for Intersection Non-Emptiness
- Title not available (Why is that?)
- A Brief History of Strahler Numbers
Cited In (9)
- State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
- The complexity of synchronizing Markov decision processes
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Title not available (Why is that?)
- Infinite Synchronizing Words for Probabilistic Automata
- Synchronizing finite automata with short reset words
- Slowly synchronizing automata with fixed alphabet size
- Regular languages of nested words: fixed points, automata, and synchronization
- Synchronizing Data Words for Register Automata
Uses Software
This page was built for publication: Synchronizing Automata over Nested Words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811343)
