uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A succinct canonical register automaton model
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Show others and affiliations
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, Published paper (Refereed)
Abstract [en]

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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6996
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-164174DOI: 10.1007/978-3-642-24372-1_26ISBN: 978-3-642-24371-4 (print)OAI: oai:DiVA.org:uu-164174DiVA: diva2:466746
Conference
Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011
Projects
ConnectUPMARC
Available from: 2011-09-30 Created: 2011-12-16 Last updated: 2013-12-21

Open Access in DiVA

No full text

Other links

Publisher's full texthttp://link.springer.com/chapter/10.1007/978-3-642-24372-1_26

Authority records BETA

Cassel, SofiaJonsson, Bengt

Search in DiVA

By author/editor
Cassel, SofiaJonsson, Bengt
By organisation
Computer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 484 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf