La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Unreachability Proofs for β Rewriting Systems by Homomorphisms Preuves d'inaccessibilité pour les systèmes de réécriture β par homomorphismes

Kiyoshi AKAMA, Yoshinori SHIGETA, Eiichi MIYAMOTO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Étant donnés deux termes et leurs règles de réécriture, un problème d'inaccessibilité prouve l'inexistence d'une séquence de réduction d'un terme à un autre. Cet article formalise une méthode pour résoudre les problèmes d'inaccessibilité par abstraction ; c'est-à-dire réduire un problème d'inaccessibilité concret original à un problème d'inaccessibilité abstrait plus simple pour prouver l'inaccessibilité du problème concret original si l'inaccessibilité abstraite est prouvée. La classe de systèmes de réécriture discutée dans cet article est appelée systèmes de réécriture β. La classe des systèmes de réécriture β comprend des systèmes très importants tels que les systèmes semi-Thue et les réseaux de Petri. Les systèmes de réécriture abstraite sont également une sous-classe des systèmes de réécriture β. Un système de réécriture β est défini sur des structures de base formulées axiomatiquement, appelées structures β, qui sont utilisées pour formaliser les concepts de « contextes » et de « remplacement », communs à de nombreux objets réécrits. Chaque domaine sous-jacent aux systèmes semi-Thue, aux réseaux de Petri et à d'autres systèmes de réécriture est formalisé par une structure β. Un concept d'homomorphismes d'une structure β (un domaine concret) à une structure β (un domaine abstrait) est introduit. Un théorème d'homomorphisme (Théorème 1) est établi pour les systèmes de réécriture β, qui stipule que l'accessibilité concrète implique l'accessibilité abstraite. Un théorème d'inaccessibilité (Corollaire 1) est également prouvé pour les systèmes de réécriture β. C'est la contraposition du théorème d'homomorphisme, c'est-à-dire qu'il dit que l'inaccessibilité abstraite implique l'inaccessibilité concrète. Le théorème d’inaccessibilité est utilisé pour résoudre deux problèmes d’inaccessibilité : un casse-tête en forme de grain de café et un casse-tête en damier.

Publication
IEICE TRANSACTIONS on Information Vol.E82-D No.2 pp.339-347
Date de publication
1999/02/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Automates, langages et théorie de l'informatique

Auteurs

Mots-clés

Table des matières