Three-way two-dimensional finite automata with rotated inputs

This paper introduces a new type of two-dimensional automaton called a three-way two-dimensional finite automaton with rotated inputs, and investigates a relationship among the accepting powers of these new automata, two-dimensional finite automata, and tape-bounded three-way two-dimensional Turing machines. We show, for example, that m log m space (m² space) is necessary and sufficient for deterministic three-way two-dimensional Turing machines to simulate deterministic (nondeterministic) three-way two-dimensional finite automata with rotated inputs.     

A note on three-dimensional finite automata

This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n²logn (n³) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n² (n²) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's.     

A note on deterministic three-way tape-bounded two-dimensional Turing machines

In this paper, we first investigate the relationship between the accepting powers of four-way two-dimensional finite automata and deterministic three-way tape-bounded two-dimensional Turing machines whose input tapes are restricted to square ones. The second part of this paper solves several open problems concerning closure properties of deterministic three-way tape-bounded two-dimensional Turing machines.     

One-way simple multihead finite automata

The first half of this paper investigates the accepting powers of various types of simple one-way multihead finite automata. It is shown that(1)for each k?1, simple one-way (k+1)-head finite automata are more powerful than simple one-way k-head finite automata.(2)for each k?2, nondeterministic simple one-way k-head finite automata are more powerful than deterministic ones, and(3)for each k?2, sensing simple one-way k-head finite automata are more powerful than non-sensing ones.In the latter half, closure properties for various types of simple one-way multihead finite automata are investigated.Finally, we demonstrate that languages accepted by nondeterministic sensing simple one-way 2-head finite automata are related to some open problem concerning deterministic and nondeterministic tape-bounded Turing computations.     

Cooperating systems of four-dimensional finite automata

M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing in 1967, and investigated their pattern recognition abilities. Since then, many researchers in this field have investigated many properties of automata on a two- or three-dimensional tape. However, the question of whether processing four-dimensional digital patterns is much more difficult than processing two- or three-dimensional ones is of great interest from both theoretical and practical standpoints. Thus, the study of four-dimensional automata as a computational model of four-dimensional pattern processing has been meaningful. This article introduces a cooperating system of four-dimensional finite automata as one model of four-dimensional automata. A cooperating system of four-dimensional finite automata consists of a finite number of four-dimensional finite automata and a four-dimensional input tape, where these finite automata work independently (in parallel). The finite automata whose input heads scan the same cell of the input tape can communicate with each other, i.e., every finite automaton is allowed to know the internal states of other finite automata on the cell it is scanning at the moment. In this article we mainly investigate the accepting powers of a cooperating system of seven-way four-dimensional finite automata. The seven-way four-dimensional finite automaton is a four-dimensional finite automaton whose input head can move east, west, south, north, up, down, or in the future, but not in the past, on a four-dimensional input tape.     

Some properties of four-dimensional multicounter automata

Recently, due to the advances in many application areas such as computer animation, motion image processing, and so forth, it has become increasingly apparent that the study of four-dimensional pattern processing is of crucial importance. Thus, we think that research into four-dimensional automata as a computational model of four-dimensional pattern processing is also meaningful. This article introduces four-dimensional multicounter automata, and investigates some of their properties. We show the differences between the accepting powers of seven-way and eight-way four-dimensional multicounter automata, and between the accepting powers of deterministic and nondeterministic seven-way four-dimensional multicounter automata. This work was presented in part at the 10th International Symposium on Artificial Life and Robotics, Oita, Japan, February 4–6, 2005     

Alternating finite automata on ω-words

Alternating finite automata on ω-words are introduced as an extension of nondeterministic finite automata which process infinite sequences of symbols. The classes of ω-languages defined by alternating finite automata are investigated and characterized under four types of acceptance conditions. It is shown that for one type of acceptance condition alternation increases the power in comparison with nondeterminism and for other three acceptance conditions nondeterministic finite automata on ω-words have the same power as alternating ones.     

Two-dimensional automata with rotated inputs (projection-type)

This paper introduces a new type of automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape x by first scanning the tape x from various sides with parallel/sequential array readers, and by then scanning the pair of the halting state configurations (i.e., projections) generated by these array readers with a multitape finite automaton. We mainly concentrate on investigating the accepting power of two-dimensional automata which consist of one-way parallel/sequential array readers and a multitape finite automaton operating in real time.     

Three-way automata on rectangular tapes over a one-letter alphabet

Necessary conditions for the languages recognized by three-way automata on tapes over a one-letter alphabet are obtained. These conditions have a simple algebraic form. Using these conditions, nondeterministic three-way automata are proved to be more powerful than deterministic automata and various decision problems for the three-way automata are solved.     

A relationship between Turing machines and finite automata on four-dimensional input tapes

Due to the advances in computer animation, motion image processing, virtual reality systems, and so forth recently, it is useful for analyzing computation of multi-dimensional information processing to explicate the properties of four-dimensional automata. From this point of view, we first proposed four-dimensional automata in 2002, and investigated their several accepting powers. In this paper, we coutinue the study, and mainly concentrate on investigating the relationship between the accepting powers of four-dimensional finite automata and seven-way four-dimensional tape-bounded Turing Machines. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Characterization of ω-regular languages by first-order formulas

First-order formulas are used to specify various ways of acceptance of ω-languages by (deterministic) finite automata, and we study the relationship between the ‘arithmetic’ hierarchy of the formulas in prenex normal form and the topological hierarchy of the accepted ω-languages. Among other things it is proved that the ω-languages accepted by finite automata under the accepting conditions specified by Σ₁-type formulas are precisely open ω-regular languages, those accepted under the conditions specified by Σ₂-type formulas coincide with the ω-regular languages which are denumerable unions of closed sets, and that as long as the accepting conditions are specified by first-order formulas the accepted ω-languages remain to be ω-regular.     

Bottom-up pyramid cellular acceptors with four-dimensional layers

In 1967, M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing. Since then, many researchers in this field have been investigating the many properties of two- or three-dimensional automata. In 1977, C.R. Dyer and A. Rosenfeld introduced an acceptor on a two-dimensional pattern (or tape) called the pyramid cellular acceptor, and demonstrated that many useful recognition tasks are executed by pyramid cellular acceptors in a time which is proportional to the logarithm of the diameter of the input. They also introduced a bottom-up pyramid cellular acceptor, which is a restricted version of the pyramid cellular acceptor, and proposed some interesting open problems about bottom-up pyramid cellular acceptors. On the other hand, we think that the study of four-dimensional automata has been meaningful as the computational model of four-dimensional information processing such as computer animation, moving picture processing, and so forth. In this article, we investigate bottom-up pyramid cellular acceptors with four-dimensional layers, and show some of their accepting powers.     

格值交替树自动机

交替（树）自动机因其本身关于取补运算的简洁性及其与非确定型（树）自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.     

Theory of one-tape linear-time Turing machines

A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power.     

Some accepting powers of three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM),¹ and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. Here, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the First European Workshop on Artificial Life and Robotics, Vienna, Austria, July 12–13, 2007     

Three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM), and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this article, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Some properties of four-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: a storage tape and an input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 7 years or so, automata on a four-dimensional tape have been proposed as computational models of four-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a four-dimensional parallel Turing machine (4-PTM), and dealt with a hardware-bounded 4-PTM in which each side-length of each input tape is equivalent. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this work, we continued the study of the 3-PTM, in which each side-length of each input tape is equivalent, and investigated some of its accepting powers.     

Path-bounded three-dimensional finite automata

The comparative study of the computational powers of deterministic and nondeterministic computations is one of the central tasks in complexity theory. This paper investigates the computational power of nondeterministic computing devices with restricted nondeterminism. There are only few results measuring the computational power of restricted nondeterminism. In general, there are three possibilities to measure the amount of nondeterminism in computation. In this paper, we consider the possibility to count the number of different nondeterministic computation paths on any input. In particular, we deal with five-way three-dimensional finite automata with multiple input heads operating on three-dimensional input tapes. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Practical CTL* model checking: Should SPIN be extended?

We describe an efficient CTL^* model checking algorithm based on alternating automata and games. A CTL^* formula, expressing a correctness property, is first translated to a hesitant alternating automaton and then composed with a Kripke structure representing the model to be checked, after which this resulting automaton is then checked for nonemptiness. We introduce the nonemptiness game that checks the nonemptiness of a hesitant alternating automaton (HAA). In the same way that alternating automata generalise nondeterministic automata, we show that this game for checking the nonemptiness of HAA, generalises the nested depth-first algorithm used to check the nonemptiness of nondeterministic Büchi automata (used in Spin).