TY - GEN

T1 - The complexity of testing ground reducibility for linear word rewriting systems with variables

AU - Kucherov, Gregory

AU - Rusinowitch, Michaël

PY - 1995

Y1 - 1995

N2 - In [9] we proved that for a word rewriting system with variables R: And a word with variables w, it is undecidable if w is ground reducible by R, that is if all the instances of w obtained by substituting its variables by non-empty words are reducible by R On the other hand, if R is linear, the question is decidable for arbitrary (linear or non-linear) w. In this paper we futher study the complexity of the above problem and prove that it is co. NP-complete if both R and w are restricted to be linear. The proof is based on the construction of a deterministic finite automaton for the language of words reducible by R The construction generalizes the well-known Aho-Corasick automaton for string matching against a set of keywords.

AB - In [9] we proved that for a word rewriting system with variables R: And a word with variables w, it is undecidable if w is ground reducible by R, that is if all the instances of w obtained by substituting its variables by non-empty words are reducible by R On the other hand, if R is linear, the question is decidable for arbitrary (linear or non-linear) w. In this paper we futher study the complexity of the above problem and prove that it is co. NP-complete if both R and w are restricted to be linear. The proof is based on the construction of a deterministic finite automaton for the language of words reducible by R The construction generalizes the well-known Aho-Corasick automaton for string matching against a set of keywords.

UR - http://www.scopus.com/inward/record.url?scp=21844503737&partnerID=8YFLogxK

U2 - 10.1007/3-540-60381-6_16

DO - 10.1007/3-540-60381-6_16

M3 - Conference contribution

AN - SCOPUS:21844503737

SN - 3540603816

SN - 9783540603818

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 262

EP - 275

BT - Conditional and Typed Rewriting Systems - 4th International Workshop, CTRS 1994, Proceedings

A2 - Dershowitz, Nachum

A2 - Lindenstrauss, Naomi

PB - Springer Verlag

T2 - 4th International Workshop on Conditional and Typed Rewriting Systems, CTRS 1994

Y2 - 13 July 1994 through 15 July 1994

ER -