Synchronizing deterministic push-down automata can be really hard
From MaRDI portal
Publication:6186317
DOI10.1016/j.ic.2023.105089OpenAlexW3021478446MaRDI QIDQ6186317
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
Publication date: 2 February 2024
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2023.105089
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular languages of nested words: fixed points, automata, and synchronization
- Quasi-rocking real-time pushdown automata
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- The equivalence and inclusion problems for NTS languages
- NTS languages are deterministic and congruential
- The complexity of decision problems for finite-turn multicounter machines
- The inclusion problem for simple languages
- Remarks on blind and partially blind one-way multicounter machines
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Decision problems for semi-Thue systems with a few rules
- Polynomial complete problems in automata theory
- Černý's conjecture and the road colouring problem
- Synchronizing words for real-time deterministic pushdown automata (extended abstract)
- Relationships between nondeterministic and deterministic tape complexities
- P(l)aying for Synchronization
- Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
- Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete
- Synchronizing Strategies under Partial Observability
- Combinatorics, Words and Symbolic Dynamics
- Adding nesting structure to words
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- The Reachability Problem for Petri Nets Is Not Elementary
- Synchronizing Automata over Nested Words
- An improvement to a recent upper bound for synchronizing words of finite automata
- Synchronizing Data Words for Register Automata
- Polynomial Time Decidability of Weighted Synchronization under Partial Observability
- Finite-Turn Pushdown Automata
- A variant of a recursively unsolvable problem
This page was built for publication: Synchronizing deterministic push-down automata can be really hard
