Absoluteness of subword inequality is undecidable
From MaRDI portal
Publication:764348
DOI10.1016/j.tcs.2011.10.017zbMath1232.68086arXiv1108.2758OpenAlexW2055195461MaRDI QIDQ764348
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.2758
undecidabilityNP-hardnessHilbert's 10th problemDiophantine equationequality problemabsoluteness problemsubword historysubword inequality
Combinatorics on words (68R15) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)
Related Items
On computational complexity of graph inference from counting, Scattered Factor-Universality of Words, Context-Freeness of Word-MIX Languages, Absent Subsequences in Words, Longest Common Subsequence with Gap Constraints, Subsequences in bounded ranges: matching and analysis problems, Absent subsequences in words, Unnamed Item, A NOTE ON THE DECIDABILITY OF SUBWORD INEQUALITIES
Cites Work