文章基本信息

标题：A Decidable Extension of Data Automata
本地全文：下载
作者：Zhilin Wu
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2011
卷号：54
页码：116-130
DOI：10.4204/EPTCS.54.9
出版社：Open Publishing Association
摘要：Data automata on data words is a decidable model proposed by Bojańczyk et al. in 2006. Class automata, introduced recently by Bojańczyk 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, Černý and Weinstein on the algorithmic analysis of array-accessing programs.