Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
From MaRDI portal
Publication:2955030
DOI10.4230/LIPIcs.STACS.2015.649zbMath1356.68068arXiv1312.6700OpenAlexW2963721241MaRDI QIDQ2955030
Publication date: 24 January 2017
Full work available at URL: https://arxiv.org/abs/1312.6700
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Undecidability and degrees of sets of sentences (03D35)
Related Items
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
