Absoluteness of subword inequality is undecidable

DOI10.1016/J.TCS.2011.10.017MaRDI QIDQ764348zbMATH OpenOpenAlexFDO

Authors Shinnosuke Seki

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

zbMATH Keywords

NP-hardnessDiophantine equationundecidabilityequality problemabsoluteness problemHilbert's 10th problemsubword historysubword inequality

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15)

Abstract: Mateescu, Salomaa, and Yu asked: is it decidable whether a given subword history assumes only non-negative values for all words over a given alphabet. In this paper, we solve this open problem by proving that this problem is undecidable even under stronger conditions than supposed originally.

Recommendations

• A note on the decidability of subword inequalities
• ON INEQUALITIES BETWEEN SUBWORD HISTORIES
• Subword histories and Parikh matrices
• On the subword equivalence problem for infinite words
• Subword histories and associated matrices

Cites work

• scientific article; zbMATH DE number 3882509 (Why is no real title available?)
• scientific article; zbMATH DE number 3693254 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 572102 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3353267 (Why is no real title available?)
• Combinatorial Pattern Matching
• Computational Complexity
• ON INEQUALITIES BETWEEN SUBWORD HISTORIES
• On Context-Free Languages
• Subword histories and Parikh matrices

Cited in

(10)

• Context-Freeness of Word-MIX Languages
• On computational complexity of graph inference from counting
• ON INEQUALITIES BETWEEN SUBWORD HISTORIES
• Longest Common Subsequence with Gap Constraints
• Absent subsequences in words
• Subsequences in bounded ranges: matching and analysis problems
• Absent Subsequences in Words
• A note on the decidability of subword inequalities
• Scattered Factor-Universality of Words
• Combinatorial algorithms for subsequence matching: a survey

This page was built for publication: Absoluteness of subword inequality is undecidable

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