zbMATH — the first resource for mathematics

The parametric ordinal-recursive complexity of Post embedding problems. (English) Zbl 1260.68179
Pfenning, Frank (ed.), Foundations of software science and computation structures. 16th international conference, FOSSACS 2013, held as part of the European joint conferences on theory and practice of software, ETAPS 2013, Rome, Italy, March 16–24, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-37074-8/pbk). Lecture Notes in Computer Science 7794, 273-288 (2013).
Summary: 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 P. Chambart and P. Schnoebelen [“The ordinal recursive complexity of lossy channel systems”, in: Proceedings of the 23rd annual IEEE symposium on logic in computer science, LICS ’08. Los Alamitos: IEEE. 205–216 (2008)] and prove parametric lower bounds depending on the size of the alphabet.
For the entire collection see [Zbl 1258.68013].

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