Intractability of decision problems for finite-memory automata

✍ Scribed by Hiroshi Sakamoto; Daisuke Ikeda

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 145 KB
• Volume: 231
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00105-x

✦ Synopsis

This paper deals with ÿnite-memory automata, introduced in Kaminski and Francez (Theoret. Comput. Sci. 134 (1994) 329-363). With a restricted memory structure that consists of a ÿnite number of registers, a ÿnite-memory automaton can store arbitrary input symbols. Thus, the language accepted by a ÿnite-memory automaton is deÿned over a potentially inÿnite alphabet.

The following decision problems are studied for a general ÿnite-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.