Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T07:19:32.438Z Has data issue: false hasContentIssue false

Efficiency of automata in semi-commutation verification techniques

Published online by Cambridge University Press:  25 September 2007

Gérard Cécé
Affiliation:
LIFC, CNRS FRE 2661, Projet INRIA-CASSIS, Université de Franche-Comté, 16 route de Gray, 25030 Besancon Cedex, France; Gerard.Cece@univ-fcomte.fr; Pierre-Cyrille.Heam@univ-fcomte.fr; Yann.Mainier@univ-fcomte.fr
Pierre-Cyrille Héam
Affiliation:
LIFC, CNRS FRE 2661, Projet INRIA-CASSIS, Université de Franche-Comté, 16 route de Gray, 25030 Besancon Cedex, France; Gerard.Cece@univ-fcomte.fr; Pierre-Cyrille.Heam@univ-fcomte.fr; Yann.Mainier@univ-fcomte.fr
Yann Mainier
Affiliation:
LIFC, CNRS FRE 2661, Projet INRIA-CASSIS, Université de Franche-Comté, 16 route de Gray, 25030 Besancon Cedex, France; Gerard.Cece@univ-fcomte.fr; Pierre-Cyrille.Heam@univ-fcomte.fr; Yann.Mainier@univ-fcomte.fr
Get access

Abstract

Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani et al. [IEEE Comput. Soc. (2001) 399–408] proved that the class of regular languages L – called APC – of the form Uj L0,j L1,j L2,j ...Lkj,j , where the union is finite and each Li,j is either a single symbol or a language of the form B* with B a subset of the alphabet, is closed under all semi-commutation relations R. Moreover a recursive algorithm on the regular expressions was given to compute R*(L). This paper provides a new approach, based on automata, for the same problem. Our approach produces a simpler and more efficient algorithm which furthermore works for a larger class of regular languages closed under union, intersection, semi-commutation relations and conjugacy. The existence of this new class, PolC, answers the open question proposed in the paper of Bouajjani et al.

Information

Type
Research Article
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable