Regularity Problems for Visibly Pushdown Languages
Regularity Problems for Visibly Pushdown Languages
复制标题
明显下推语言的正则性问题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
O. Serre
中科院分区：
文献类型：
--
作者：
V. Bárány;Christof Löding;O. Serre
可见下推自动机是一种特殊的下推自动机，其堆栈行为由输入符号按照字母表的划分来驱动。我们表明，它是可判定的一个给定的明显下推自动机是否相当于一个明显的计数器自动机，即一个自动机，它的堆栈只作为计数器。特别地，这允许决定给定的可见下推语言是否是匹配良好的词的集合的常规限制，这意味着如果仅匹配良好的词被认为是输入，则该语言可以被有限自动机接受。
Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.