Back to Search Start Over

Absoluteness of subword inequality is undecidable

Authors :
Seki, Shinnosuke
Publication Year :
2011

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.

Subjects

Subjects :
Computer Science - Formal Languages and Automata Theory
68Q17, 68Q45

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1108.2758
Document Type :
Working Paper

Tools

Authors Abstract Subjects Details