Grigore, Radu and Tzevelekos, Nikos - History-Register Automata

lmcs:1630 - Logical Methods in Computer Science, March 29, 2016, Volume 12, Issue 1
History-Register Automata

Authors: Grigore, Radu and Tzevelekos, Nikos

Programs with dynamic allocation are able to create and use an unbounded number of fresh resources, such as references, objects, files, etc. We propose History-Register Automata (HRA), a new automata-theoretic formalism for modelling such programs. HRAs extend the expressiveness of previous approaches and bring us to the limits of decidability for reachability checks. The distinctive feature of our machines is their use of unbounded memory sets (histories) where input symbols can be selectively stored and compared with symbols to follow. In addition, stored symbols can be consumed or deleted by reset. We show that the combination of consumption and reset capabilities renders the automata powerful enough to imitate counter machines, and yields closure under all regular operations apart from complementation. We moreover examine weaker notions of HRAs which strike different balances between expressiveness and effectiveness.


Source : oai:arXiv.org:1209.0680
DOI : 10.2168/LMCS-12(1:7)2016
Volume: Volume 12, Issue 1
Published on: March 29, 2016
Submitted on: September 10, 2015
Keywords: Computer Science - Programming Languages,Computer Science - Formal Languages and Automata Theory


Share

Consultation statistics

This page has been seen 149 times.
This article's PDF has been downloaded 115 times.