Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-06-07
EPTCS 54, 2011, pp. 116-130
Computer Science
Formal Languages and Automata Theory
In Proceedings GandALF 2011, arXiv:1106.0814
Scientific paper
10.4204/EPTCS.54.9
Data automata on data words is a decidable model proposed by Boja\'nczyk et al. in 2006. Class automata, introduced recently by Boja\'nczyk and Lasota, is an extension of data automata which unifies different automata models on data words. The nonemptiness of class automata is undecidable, since class automata can simulate two-counter machines. In this paper, a decidable model called class automata with priority class condition, which restricts class automata but strictly extends data automata, is proposed. The decidability of this model is obtained by establishing a correspondence with priority multicounter automata. This correspondence also completes the picture of the links between various class conditions of class automata and various models of counter machines. Moreover, this model is applied to extend a decidability result of Alur, Cern\'y and Weinstein on the algorithmic analysis of array-accessing programs.
No associations
LandOfFree
A Decidable Extension of Data Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Decidable Extension of Data Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Decidable Extension of Data Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-25268