Paper Info
Title
On the average size of glushkov and equation automata for KAT expressions
Abstract
Kleene algebra with tests (KAT) is an equational system that extends Kleene algebra, the algebra of regular expressions, and that is specially suited to capture and verify properties of simple imperative programs. In this paper we study two constructions of automata from KAT expressions: the Glushkov automaton ($\mathcal{A}_{\mathsf{pos}}$), and a new construction based on the notion of prebase (equation automata, $\mathcal{A}_{\mathsf{eq}}$). Contrary to other automata constructions from KAT expressions, these two constructions enjoy the same descriptional complexity behaviour as their counterparts for regular expressions, both in the worst-case as well as in the average-case. In particular, our main result is to show that, asymptotically and on average the number of transitions of the $\mathcal{A}_{{\mathsf{pos}}}$ is linear in the size of the KAT expression.
Year
DOI
Venue
2013
10.1007/978-3-642-40164-0_10
FCT
Keywords
Field
DocType
main result,automata construction,equation automaton,descriptional complexity behaviour,kleene algebra,average size,equational system,new construction,regular expression,glushkov automaton,kat expression
Kleene algebra,Discrete mathematics,Combinatorics,Regular expression,Expression (mathematics),Automaton,Mathematics
Conference
Citations 
PageRank 
References 
3
0.39
8
Authors
4
Name
Order
Citations
PageRank
Sabine Broda16413.83
António Machiavelo2458.82
Nelma Moreira318033.98
Rogério Reis414025.74