On ground reducibility problem for word rewriting systems with variables

Gregory Kucherov, Michael Rusinowitch

Результат исследований: Глава в книге, отчете, сборнике статейМатериалы для конференциирецензирование

2 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаАнглийский
Название основной публикации1994 ACM Symposium on Applied Computing, SAC 1994
ИздательAssociation for Computing Machinery
Страницы271-276
Число страниц6
ISBN (электронное издание)0897916476
DOI
СостояниеОпубликовано - 6 апр. 1994
Опубликовано для внешнего пользованияДа
Событие1994 ACM Symposium on Applied Computing, SAC 1994 - Phoenix, Соединенные Штаты Америки
Продолжительность: 6 мар. 19948 мар. 1994

Серия публикаций

НазваниеProceedings of the ACM Symposium on Applied Computing
ТомPart F129433

Конференция

Конференция1994 ACM Symposium on Applied Computing, SAC 1994
Страна/TерриторияСоединенные Штаты Америки
ГородPhoenix
Период6/03/948/03/94

Fingerprint

Подробные сведения о темах исследования «On ground reducibility problem for word rewriting systems with variables». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать