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

Reduction of Register Pushdown Systems with Freshness Property to Pushdown Systems in LTL Model Checking Réduction des systèmes pushdown de registre avec la propriété Freshness aux systèmes pushdown dans la vérification de modèle LTL

Yoshiaki TAKATA, Ryoma SENDA, Hiroyuki SEKI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le système pushdown de registre (RPDS) est une extension du système pushdown (PDS) qui dispose de registres pour traiter les valeurs de données. Une méthode de vérification de modèle LTL pour les RPDS avec des évaluations régulières a été proposée dans des travaux antérieurs ; cependant, la méthode nécessite que les automates de registre (RA) utilisés pour définir une évaluation régulière soient déterministes en arrière. Cet article propose une autre approche du même problème, dans laquelle le problème de vérification de modèle pour RPDS est réduit à celui pour PDS en construisant une bisimulation PDS équivalente à un RPDS donné. Cette construction est plus simple que la méthode de vérification de modèle précédente et ne nécessite pas d'AR déterministe ou rétro-déterministe, et l'équivalence de bisimulation garantit clairement l'exactitude de la réduction. D'un autre côté, la méthode proposée nécessite que chaque RPDS (et RA) ait la propriété de fraîcheur, dans laquelle chaque fois que le RPDS met à jour un registre avec une valeur de données non stockée dans aucun registre ou dans le sommet de la pile, la valeur doit être fraîche. Cet article montre également que le problème de vérification de modèle avec des valuations régulières définies par le RA général est indécidable, et donc la contrainte de fraîcheur est essentielle dans la méthode proposée.

Publication
IEICE TRANSACTIONS on Information Vol.E105-D No.9 pp.1620-1623
Date de publication
2022/09/01
Publicisé
2022/05/27
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2022EDL8030
Type de manuscrit
LETTER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

Yoshiaki TAKATA
  Kochi University of Technology
Ryoma SENDA
  Nagoya University
Hiroyuki SEKI
  Nagoya University

Mots-clés

Table des matières