Synchronizing deterministic push-down automata can be really hard

DOI10.1016/J.IC.2023.105089MaRDI QIDQ6186317zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

complexitydeterministic push-down automatasynchronization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Synchronizing deterministic push-down automata can be really hard
• Synchronization of Pushdown Automata
• Complexity of checking whether two automata are synchronized by the same language
• Synchronization of Parikh automata
• Synchronization of automata with one undefined or ambiguous transition

Cites work

• A note on homogeneous experiments with finite automata
• A remark about homogeneous experiments
• A variant of a recursively unsolvable problem
• Adding nesting structure to words
• An improvement to a recent upper bound for synchronizing words of finite automata
• Combinatorics, Words and Symbolic Dynamics
• 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
• Finite-Turn Pushdown Automata
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3266647 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 7730619 (Why is no real title available?)
• Language equivalence of deterministic real-time one-counter automata is NL-complete
• NTS languages are deterministic and congruential
• Polynomial complete problems in automata theory
• Polynomial time decidability of weighted synchronization under partial observability
• Quasi-rocking real-time pushdown automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Regular languages of nested words: fixed points, automata, and synchronization
• Relationships between nondeterministic and deterministic tape complexities
• Remarks on blind and partially blind one-way multicounter machines
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing automata over nested words
• Synchronizing data words for register automata
• Synchronizing deterministic push-down automata can be really hard
• Synchronizing strategies under partial observability
• Synchronizing words for real-time deterministic pushdown automata (extended abstract)
• The complexity of decision problems for finite-turn multicounter machines
• The equivalence and inclusion problems for NTS languages
• The inclusion problem for simple languages
• The Reachability Problem for Petri Nets Is Not Elementary
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Černý's conjecture and the road colouring problem

Cited in

(3)

• Synchronizing deterministic push-down automata can be really hard
• Synchronization of Parikh automata
• Synchronization of Parikh automata

This page was built for publication: Synchronizing deterministic push-down automata can be really hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186317)