The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
classification
💻 cs.LO
keywords
embeddingproblemsboundscomplexitylowerparametricpostprove
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.