Decidability of Identity-free Relational Kleene Lattices

Abstract : Families of binary relations are important interpretations of regular expressions, and the equivalence of two regular expressions with respect to their relational interpretations is decidable: the problem reduces to the equality of the denoted regular languages. Putting together a few results from the literature, we first make explicit a generalisation of this reduction, for regular expressions extended with converse and intersection: instead of considering sets of words (i.e., formal languages), one has to consider sets of directed and labelled graphs. We then focus on identity-free regular expressions with intersection—a setting where the above graphs are acyclic—and we show that the corresponding equational theory is decidable. We achieve this by defining an automaton model, based on Petri Nets, to recognise these sets of acyclic graphs, and by providing an algorithm to compare such automata.
Type de document :
Communication dans un congrès
David Baelde; Jade Alglave. Vingt-sixièmes Journées Francophones des Langages Applicatifs (JFLA 2015), Jan 2015, Le Val d'Ajol, France. Actes des Vingt-sixièmes Journées Francophones des Langages Applicatifs (JFLA 2015), 〈http://jfla.inria.fr/2015〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01099137
Contributeur : David Baelde <>
Soumis le : mercredi 31 décembre 2014 - 15:42:46
Dernière modification le : mercredi 7 janvier 2015 - 01:13:04
Document(s) archivé(s) le : mercredi 1 avril 2015 - 10:26:17

Fichier

jfla15_submission_30.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01099137, version 1

Collections

Citation

Paul Brunet, Damien Pous. Decidability of Identity-free Relational Kleene Lattices. David Baelde; Jade Alglave. Vingt-sixièmes Journées Francophones des Langages Applicatifs (JFLA 2015), Jan 2015, Le Val d'Ajol, France. Actes des Vingt-sixièmes Journées Francophones des Langages Applicatifs (JFLA 2015), 〈http://jfla.inria.fr/2015〉. 〈hal-01099137〉

Partager

Métriques

Consultations de
la notice

118

Téléchargements du document

77