Confluence of Prefix-Constrained Rewrite Systems
| Autor: | Andrianarivelo, Nirina, Réty, Pierre |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Andrianarivelo, Nirina |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
000 Computer science knowledge general works TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Computer Science [INFO]Computer Science [cs] [INFO] Computer Science [cs] ACM: F.: Theory of Computation ComputingMilieux_MISCELLANEOUS |
| Zdroj: | 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018) 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018), Jul 2018, Oxford, United Kingdom |
| Popis: | Prefix-constrained rewriting is a strict extension of context-sensitive rewriting. We study the confluence of prefix-constrained rewrite systems, which are composed of rules of the form L: l -> r where L is a regular string language that defines the allowed rewritable positions. The usual notion of Knuth-Bendix's critical pair needs to be extended using regular string languages, and the convergence of all critical pairs is not enough to ensure local confluence. Thanks to an additional restriction we get local confluence, and then confluence for terminating systems, which makes the word problem decidable. Moreover we present an extended Knuth-Bendix completion procedure, to transform a non-confluent prefix-constrained rewrite system into a confluent one. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|