On ground reducibility problem for word rewriting systems with variables

Gregory Kucherov, Michael Rusinowitch

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

2 Citations (Scopus)

Abstract

Given a word rewriting system with variables R and a word with variables w, the question we are interested in is whether all the instances of w obtained by substituting its variables by non-empty words are reducible by R. This property is known as ground reducibility and is the core of the inductive completion methods that have been designed for proving theorems in the initial model of equational specifications. We prove the problem to be generally undecidable even for a very simple word w, namely axa where a is a letter and x a variable. When R is left-linear, the question is decidable for arbitrary (linear or non-linear) w.

Original languageEnglish
Title of host publication1994 ACM Symposium on Applied Computing, SAC 1994
PublisherAssociation for Computing Machinery
Pages271-276
Number of pages6
ISBN (Electronic)0897916476
DOIs
Publication statusPublished - 6 Apr 1994
Externally publishedYes
Event1994 ACM Symposium on Applied Computing, SAC 1994 - Phoenix, United States
Duration: 6 Mar 19948 Mar 1994

Publication series

NameProceedings of the ACM Symposium on Applied Computing
VolumePart F129433

Conference

Conference1994 ACM Symposium on Applied Computing, SAC 1994
Country/TerritoryUnited States
CityPhoenix
Period6/03/948/03/94

Keywords

  • Decidability
  • Pattern languages
  • Rewriting
  • String matching

Fingerprint

Dive into the research topics of 'On ground reducibility problem for word rewriting systems with variables'. Together they form a unique fingerprint.

Cite this