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

Gregory Kucherov, Michaël Rusinowitch

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationConditional and Typed Rewriting Systems - 4th International Workshop, CTRS 1994, Proceedings
EditorsNachum Dershowitz, Naomi Lindenstrauss
PublisherSpringer Verlag
Pages262-275
Number of pages14
ISBN (Print)3540603816, 9783540603818
DOIs
Publication statusPublished - 1995
Externally publishedYes
Event4th International Workshop on Conditional and Typed Rewriting Systems, CTRS 1994 - Jerusalem, Israel
Duration: 13 Jul 199415 Jul 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume968
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Workshop on Conditional and Typed Rewriting Systems, CTRS 1994
Country/TerritoryIsrael
CityJerusalem
Period13/07/9415/07/94

Fingerprint

Dive into the research topics of 'The complexity of testing ground reducibility for linear word rewriting systems with variables'. Together they form a unique fingerprint.

Cite this