Algorithms and Reductions for Rewriting Problems

Rakesh M. Verma; Michaël Rusinowitch; Denis Lugiez

inria-00073431, version 1

Algorithms and Reductions for Rewriting Problems

Rakesh M. Verma ¹, Michaël Rusinowitch ¹, Denis Lugiez ¹

N° RR-3258 (1997)

Résumé : In this paper we initiate a systematic study of polynomial-time reductions for some basic decision problems of rewrite systems. We then give a polynomial-time algorithm for Unique-normal-form property of ground systems for the first time. Next we prove undecidability of these problems for string rewriting using our reductions. Finally, we prove partial decidability results for Confluence of commutative semi-thue systems. The Confluence and Unique-normal-form property are also shown Expspace-hard for commutative semi-thue systems.

1 : PROTHEO (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00073431, version 1
http://hal.inria.fr/inria-00073431
oai:hal.inria.fr:inria-00073431
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mercredi 24 Mai 2006, 12:47:24
Dernière modification le : Mercredi 17 Janvier 2007, 17:26:04

Voir la fiche détaillée

Documents associés

PS :

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00073431"><monogr>
<author><persName><forename>Rakesh M.</forename><surname>Verma</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">PROTHEO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Michaël</forename><surname>Rusinowitch</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">PROTHEO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Denis</forename><surname>Lugiez</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">PROTHEO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="m">Algorithms and Reductions for Rewriting Problems</title><title type="main" level="m">Algorithms and Reductions for Rewriting Problems</title><imprint><biblScope type="publicationDate">1997-00-00</biblScope><biblScope type="pp">21</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00073431</idno><idno type="HALFile">http://hal.inria.fr/inria-00073431/PDF/RR-3258.pdf</idno></biblStruct>
</listBibl>
</listBibl>