Intractability of decision problems for finite-memory automata
Intractability of decision problems for finite-memory automata
复制标题
DOI：
10.1016/s0304-3975(99)00105-x
复制
发表时间：
2000-01-28
影响因子：
1.1
通讯作者：
Ikeda, D
中科院分区：
文献类型：
--
作者：
Sakamoto, H;Ikeda, D
本文论述了有限记忆自动机，介绍了卡明斯基和弗朗兹（理论。Sci. 134（1994）329-363）。有限记忆自动机是由有限数量的寄存器组成的有限记忆结构，它可以存储任意的输入符号。因此，有限记忆自动机所接受的语言是在潜在的无限字母表上定义的。本文研究了一般有限记忆自动机A和确定性自动机A的下列判定问题：隶属度问题，即给定一个A和一个字符串w，来决定w是否被A接受，以及非空性问题，即，给定一个A，判断A所接受的语言是否为非空。成员资格问题是P-完全的，只要给定的自动机是确定性的，并且其他每个问题都是NP-完全的。因此，我们得出结论，认为决策问题是棘手的。(C)2000 Elsevier Science B. V.保留所有权利。
This paper deals with finite-memory automata, introduced in Kaminski and Francez (Theoret. Comput. Sci. 134 (1994) 329-363). With a restricted memory structure that consists of a finite number of registers, a finite-memory automaton can store arbitrary input symbols. Thus, the language accepted by a finite-memory automaton is defined over a potentially infinite alphabet. The following decision problems are studied for a general finite-memory automata A as well as for deterministic ones: the membership problem, i.e., given an A and a string w, to decide whether w is accepted by A, and the non-emptiness problem, i.e., given an A, to decide whether the language accepted by A is non-empty. The membership problem is P-complete, provided a given automaton is deterministic, and each of the other problems is NP-complete. Thus, we conclude that the decision problems considered are intractable. (C) 2000 Elsevier Science B.V. All rights reserved.