Consistency problem for one-variable patterns is polynomially decidable - Collections

＜technical report＞
Consistency problem for one-variable patterns is polynomially decidable

Creator	Author PID K000167 Creator Name Sakamoto, Hiroshi 坂本, 比呂志 Affiliation Affiliation Name Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門
Language	English
Publisher	Department of Informatics, Kyushu University
Publisher	九州大学大学院システム情報科学研究院情報理学部門
Date	1998-05
Source Title	DOI Technical Report
Vol	150
Publication Type	Accepted Manuscript
Access Rights	open access
Related DOI	DOI Technical Report \|\| 150
Related DOI	http://www.i.kyushu-u.ac.jp/research/report.html
Related URI	DOI Technical Report \|\| 150
Related URI	http://www.i.kyushu-u.ac.jp/research/report.html
Relation	DOI Technical Report \|\| 150
Relation	http://www.i.kyushu-u.ac.jp/research/report.html
Abstract	The present paper deals with the decision problem for the class of one-variable patterns, called the consistency problem. Although this problem is obviously in NP, its tractability is unknown. We prov...e the consistency problem to be decidable in P.show more

File	FileType	Size	Views	Description
trcs150	pdf	177 KB	98
trcs150.ps	gz	81.5 KB	51