Absoluteness of subword inequality is undecidable

DOI10.1016/J.TCS.2011.10.017zbMATH Open1232.68086arXiv1108.2758OpenAlexW2055195461MaRDI QIDQ764348FDOQ764348

Shinnosuke Seki

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1108.2758

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

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)

Cites Work

• Title not available (Why is that?)
• Computational Complexity
• On Context-Free Languages
• Subword histories and Parikh matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial Pattern Matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• ON INEQUALITIES BETWEEN SUBWORD HISTORIES
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• 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

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)