scientific article; zbMATH DE number 7559404

DOI10.4230/LIPIcs.MFCS.2020.33MaRDI QIDQ5089200

Tomoyuki Yamakami, Henning Fernau, Petra Wolf

Publication date: 18 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computational complexitycomputabilitysynchronizing automatonreset sequencefinite-turn push-down automatonreal-time deterministic push-down automaton

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (5)

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 ⋮ Synchronizing words for real-time deterministic pushdown automata (extended abstract)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Automata, languages and programming. Seventh Colloquium, Noordwijkerhout, the Netherlands, July 14-18, 1980
• 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
• Model-based testing of reactive systems. Advanced lectures.
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• An improvement to a recent upper bound for synchronizing words of finite automata
• Switching and Finite Automata Theory
• Finite-Turn Pushdown Automata
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• A variant of a recursively unsolvable problem

This page was built for publication: