Skip to Main content Skip to Navigation
Reports

On the ground reducibility problem for word rewriting systems with variables

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. We prove this 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).
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074779
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:17:39 PM
Last modification on : Thursday, February 11, 2021 - 2:48:31 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:19:59 PM

Identifiers

  • HAL Id : inria-00074779, version 1

Collections

Citation

Gregory Kucherov, Michaël Rusinowitch. On the ground reducibility problem for word rewriting systems with variables. [Research Report] RR-1892, INRIA. 1993. ⟨inria-00074779⟩

Share

Metrics

Record views

203

Files downloads

177