On the Average Size of Glushkov and Equation Automata for KAT Expressions

Autor:	Nelma Moreira, Sabine Broda, António Machiavelo, Rogério Reis
Rok vydání:	2013
Předmět:	Kleene algebra Discrete mathematics Combinatorics Equational system Average size Simple (abstract algebra) Regular expression Algebra over a field Computer Science::Formal Languages and Automata Theory Expression (mathematics) Mathematics Automaton
Zdroj:	Fundamentals of Computation Theory ISBN: 9783642401633 FCT
DOI:	10.1007/978-3-642-40164-0_10
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3431eaf3f301a64a547eaf242d3ffcab https://doi.org/10.1007/978-3-642-40164-0_10 Zobrazit plný text záznamu