A succinct canonical register automaton model
2011 (English)In: Automated Technology for Verification and Analysis: ATVA 2011 / [ed] Tevfik Bultan, Pao-Ann Hsiung, Berlin: Springer-Verlag , 2011, 366-380 p.Conference paper (Refereed)
We present a novel canonical automaton model, based on register automata, that can easily be used to specify protocol or program behavior. More concretely, register automata are reminiscent of controlflow graphs: they comprise a finite control structure, assignments, and conditionals, allowing to assign values of an infinite domain to regis-ters (variables) and to compare them for equality. A major contributionis the definition of a canonical automaton representation of any lan-guage recognizable by a deterministic register automaton, by means of aNerode congruence. Not only is this canonical form easier to comprehend than previous proposals, but it can also be exponentially more succinct than these. Key to the canonical form is the symbolic treatment of data languages, which overcomes the structural restrictions in previous formalisms, and opens the way to new practical applications.
Place, publisher, year, edition, pages
Berlin: Springer-Verlag , 2011. 366-380 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 6996
Research subject Computer Science
IdentifiersURN: urn:nbn:se:uu:diva-164174DOI: 10.1007/978-3-642-24372-1_26ISBN: 978-3-642-24371-4OAI: oai:DiVA.org:uu-164174DiVA: diva2:466746
Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011