Synchronizing deterministic push-down automata can be really hard

DOI10.4230/LIPICS.MFCS.2020.33MaRDI QIDQ5089200zbMATH OpenFDO

Authors Henning Fernau, Petra Wolf, Tomoyuki Yamakami

Publication date 18 July 2022

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

zbMATH Keywords

computabilitycomputational complexityfinite-turn push-down automatonreal-time deterministic push-down automatonreset sequencesynchronizing automaton

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 remark about homogeneous experiments
• A variant of a recursively unsolvable problem
• An improvement to a recent upper bound for synchronizing words of finite automata
• Automata, languages and programming. Seventh Colloquium, Noordwijkerhout, the Netherlands, July 14-18, 1980
• 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
• Directable nondeterministic automata
• Finite-Turn Pushdown Automata
• scientific article; zbMATH DE number 7228447 (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 3310084 (Why is no real title available?)
• Model-based testing of reactive systems. Advanced lectures.
• Polynomial complete problems in automata theory
• Quasi-rocking real-time pushdown automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Remarks on blind and partially blind one-way multicounter machines
• Reset Sequences for Monotonic Automata
• Switching and Finite Automata Theory
• Synchronizing Automata and the Černý Conjecture
• Synchronizing weighted automata
• Synchronizing words for weighted and timed automata
• 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 Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words

Cited in

(5)

• Synchronizing words for real-time deterministic pushdown automata (extended abstract)
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• Synchronization of Parikh automata
• Formal grammars for turn-bounded deterministic context-free languages
• Synchronizing deterministic push-down automata can be really hard

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 Q5089200)