Petri automata
Kleene algebra axioms are complete with respect to both language models and binary relation models. In particular, two regular expressions recognise the same language if and only if they are universally equivalent in the model of binary relations. We consider Kleene allegories, i.e., Kleene algebras with two additional operations and a constant which are natural in binary relation models: intersection, converse, and the full relation. While regular languages are closed under those operations, the above characterisation breaks. Putting together a few results from the literature, we give a characterisation in terms of languages of directed and labelled graphs. By taking inspiration from Petri nets, we design a finite automata model, Petri automata, allowing to recognise such graphs. We prove a Kleene theorem for this automata model: the sets of graphs recognisable by Petri automata are precisely the sets of graphs definable through the extended regular expressions we consider. Petri automata allow us to obtain decidability of identityfree relational Kleene lattices, i.e., the equational theory generated by binary relations on the signature of regular expressions with intersection, but where one forbids unit. This restriction is used to ensure that the corresponding graphs are acyclic. We actually show that this decision problem is EXPSPACEcomplete.
Related talks  
The Equational Theory of Positive Relation Algebra
MOVE
in Marseille,
March 2017
.

More  
The Equational Theory of Positive Relation Algebra
PACE
in Shanghai,
November 2016
.

More  
A Kleene Theorem for Petri automata
Highlights
in Brussels,
September 2016
.

More  
Une introduction aux algèbres de Kleene
Inter'Actions
in Lyon,
May 2016
(in French)
.

More  
Petri automata for Kleene Allegories
LiCS
in Kyoto,
July 2015
.

More  
Petri automata for Kleene allegories
Rapido
in Paris,
June 2015
.

More  
Petri automata for Kleene allegories
Midlands Graduate School
in Sheffield,
April 2015
.

More  
Décidabilité des Treillis de Kleene sans identité
JFLA
in Val d'Ajol,
January 2015
(in French)
.

More  
Decidability of Identityfree Kleene Lattices
LAC
in Chambéry,
November 2014
.

More  
Kleene Algebra with Converse
RAMiCS
in Marienstatt,
April 2014
.

More  
Deciding Kleene Algebra with converse is PSpacecomplete
GeoCal
in Bordeaux,
March 2014
.

More  
Deciding Kleene Algebra with converse is PSpacecomplete
PACE
in Lyon,
February 2014
.

More  
Algèbres de Relations, Étude des algèbres de Kleene avec converse
Internship defence
in Paris,
September 2013
(Internship defence, in French)
.

More  
Equivalence of regular expressions with converse on relations
PiCoq
in Lyon,
June 2013
.

More  
Related papers  
Cardinalities of finite relations in Coq
(in ITP 2016)
with Insa Stucke and Damien Pous. 
More  
Algorithms for Kleene algebra with converse
(in JLAMP 2016)
with Damien Pous. 
More  
Algebras of relations: from algorithms to formal proofs (in Université de Lyon 2016)  More  
Petri automata for Kleene allegories
(in LICS 2015)
with Damien Pous. 
More  
Decidability of identityfree relational Kleene lattices
(in JFLA 2015)
with Damien Pous. 
More  
Kleene algebra with converse
(in RAMICS 2014)
with Damien Pous. 
More 