The Library
Weak and nested class memory automata
Tools
Cotton-Barratt, Conrad, Murawski, Andrzej S. and Ong, Luke (2015) Weak and nested class memory automata. In: Horia Dediu, Adrian and Formenti, Enrico, 1968- and Martín Vide, Carlos and Truthe, Bianca, (eds.) Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. Lecture Notes in Computer Science (Volume 8977). Berlin ; Heidelberg: Springer International Publishing, pp. 188-199. ISBN 9783319155784
|
PDF
WRAP_1271755-cs-090715-paper_57.pdf - Accepted Version - Requires a PDF viewer. Download (592Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-319-15579-1_14
Abstract
Automata over infinite alphabets have recently come to be studied extensively as potentially useful tools for solving problems in verification and database theory. One popular model of automata studied is the Class Memory Automata (CMA), for which the emptiness problem is equivalent to Petri Net Reachability. We identify a restriction – which we call weakness – of CMA, and show that they are equivalent to three existing forms of automata over data languages. Further, we show that in the deterministic case they are closed under all Boolean operations, and hence have an ExpSpace-complete equivalence problem. We also extend CMA to operate over multiple levels of nested data values, and show that while these have undecidable emptiness in general, adding the weakness constraint recovers decidability of emptiness, via reduction to coverability in well-structured transition systems. We also examine connections with existing automata over nested data.
Item Type: | Book Item | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Robots, Data processing | ||||||
Series Name: | Lecture Notes in Computer Science | ||||||
Publisher: | Springer International Publishing | ||||||
Place of Publication: | Berlin ; Heidelberg | ||||||
ISBN: | 9783319155784 | ||||||
ISSN: | 0302-9743 | ||||||
Book Title: | Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings | ||||||
Editor: | Horia Dediu, Adrian and Formenti, Enrico, 1968- and Martín Vide, Carlos and Truthe, Bianca | ||||||
Official Date: | 24 February 2015 | ||||||
Dates: |
|
||||||
Number: | Volume 8977 | ||||||
Page Range: | pp. 188-199 | ||||||
DOI: | 10.1007/978-3-319-15579-1_14 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 30 December 2015 | ||||||
Date of first compliant Open Access: | 27 February 2016 | ||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), Merton College | ||||||
Grant number: | EP/J019577/1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year