The parametric ordinal-recursive complexity of Post embedding problems

DOI10.1007/978-3-642-37075-5_18MaRDI QIDQ4910425zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Abstract: Post Embedding Problems are a family of decision problems based on the interaction of a rational relation with the subword embedding ordering, and are used in the literature to prove non multiply-recursive complexity lower bounds. We refine the construction of Chambart and Schnoebelen (LICS 2008) and prove parametric lower bounds depending on the size of the alphabet.

Recommendations

• Pumping and counting on the regular Post embedding problem
• The ω-Regular Post Embedding Problem
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems

Cited in

(8)

• The parameterized space complexity of embedding along a path
• Complexity hierarchies beyond elementary
• Pumping and counting on the regular Post embedding problem
• The Parametric Complexity of Lossy Counter Machines
• Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
• The ω-Regular Post Embedding Problem
• The ideal view on Rackoff's coverability technique
• Branching in well-structured transition systems (invited talk)

This page was built for publication: The parametric ordinal-recursive complexity of Post embedding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910425)