The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
From MaRDI portal
Publication:4910425
DOI10.1007/978-3-642-37075-5_18zbMath1260.68179arXiv1211.5259OpenAlexW3105504905MaRDI QIDQ4910425
Sylvain Schmitz, Prateek Karandikar
Publication date: 18 March 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.5259
Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Recursive functions and relations, subrecursive hierarchies (03D20)
Related Items (5)
Zeno, Hercules, and the Hydra ⋮ The ideal view on Rackoff's coverability technique ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary ⋮ Generalized Post embedding problems
This page was built for publication: The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
