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

• Type: Article in International Conference Proceedings Book
• Date: 2013

Authors

Broda, S (Author) FCUP; Machiavelo, A (Author) FCUP; Moreira, N (Author) FCUP; Reis, R (Author) FCUP

Conference proceedings International

Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Pages: 72-83

19th International Symposium on Fundamentals of Computation Theory, FCT 2013

Liverpool, 19 August 2013 through 21 August 2013

Indexing

ISI Web of Knowledge

ISI Web of Science

Scopus - 9 Citations

Scientific classification

CORDIS: Technological sciences

Associated Projects

Centro de Matemática da Universidade do Porto - Centro de Matemática da Universidade do Porto

Other information

Authenticus ID: P-008-DF9

DOI: 10.1007/978-3-642-40164-0_10

Abstract (EN): 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 (Apos), and a new construction based on the notion of prebase (equation automata, Aeq). 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 A pos is linear in the size of the KAT expression. © 2013 Springer-Verlag.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12