Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words

DOI10.4230/LIPIcs.STACS.2015.649zbMath1356.68068arXiv1312.6700OpenAlexW2963721241MaRDI QIDQ2955030

Turlough Neary

Publication date: 24 January 2017

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

zbMATH Keywords

undecidabilityPost correspondence problemtag system

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Undecidability and degrees of sets of sentences (03D35)

Related Items (18)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ Parsimonious computational completeness ⋮ Variations on the post correspondence problem for free groups ⋮ Integer weighted automata on infinite words ⋮ Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time ⋮ Integer Weighted Automata on Infinite Words ⋮ Post's correspondence problem: from computer science to algebra ⋮ What else is undecidable about loops? ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ On bi-infinite and conjugate post correspondence problems ⋮ Post's Correspondence Problem for hyperbolic and virtually nilpotent groups ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ Unnamed Item ⋮ Reachability problems in low-dimensional nondeterministic polynomial maps over integers ⋮ On Affine Reachability Problems ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ Average-Case Completeness in Tag Systems

This page was built for publication: Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words