Access count of this item: 76

Files in This Item:
File Description SizeFormat 
j.tcs.2011.10.017.pdf70.49 kBAdobe PDFView/Open
Title: Absoluteness of subword inequality is undecidable
Authors: Seki, Shinnosuke
Author's alias: 関, 新之助
Keywords: Subword history
Subword inequality
Hilbert’s 10th problem
Diophantine equation
Undecidability
NP-hardness
Issue Date: Feb-2012
Publisher: Elsevier B.V.
Journal title: Theoretical Computer Science
Volume: 418
Start page: 116
End page: 120
Abstract: In a given word, one can count the number of occurrences of other words as a scattered subword. These counts can be “added” and/or “multiplied.” A subword history gives an instruction of what words to be counted and how these counts to be added and multiplied with other counts or integer constants, and hence, determines its unique value in a given word. Mateescu, Salomaa, and Yu asked: “is it decidable whether the value of a given subword history is non-negative in all words over a given alphabet?” (absoluteness problem). Another important problem is of whether there exists a word in which the value of a given subword history becomes 0 (equality problem). In this paper, we prove the undecidability of the equality problem and show that the equality problem is polynomial-time Karp reducible to the absoluteness problem; thus, the absoluteness problem is also undecidable. This approach solves the open problem actually under stronger conditions than supposed originally.
Rights: © 2011 Elsevier B.V.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/154037
DOI(Published Version): 10.1016/j.tcs.2011.10.017
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.