Two-dimensional automata with rotated inputs

This paper introduces a new type of automata on a two-dimensional tape, which decides acceptance or rejection of an input tape x by scanning the tape x from various sides by various automata. The accepting power of such an automaton is investigated. This paper mainly concentrates on investigating the accepting power of two-dimensional automata which consist of four parallel/sequential array automata, say M₁, M₂, M₃, and M₄, and which accept an input tape x if and only if x, x^R, (x^R)^R, and ((x^R)^R)^R are accepted by M₁, M₂, M₃, and M₄, respectively, where for any tape y, y^R is the tape obtained by rotating y clockwise 90°.     

Cyclic closure properties of automata on a two-dimensional tape

In this paper, we investigate cyclic closure properties of several types of automata on a two-dimensional tape. It is shown that (1) the classes of sets accepted by two-dimensional finite automata, deterministic one-way parallel/sequential array automata, and two-dimensional deterministic on-line tessellation acceptors are not closed under row or column cyclic closure, and (2) the class of sets accepted by two-way parallel-sequential array automata is not closed under row cyclic closure.     

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.     

Multiple equality sets and post machines

Equality sets of finite sets of homomorphisms are studied as part of formal language theory. Some particular equality sets, called Merge_k(k-COPY), are investigated. These languages are combinatorially difficult, and are full semiAFL generators of the recursively enumerable sets, and are semiAFL generators of the class MULTI-RESET, provided k ? 3. To accomplish this characterization, equality sets are related to multihead and multitape Post machines operating in real time. A Post machine has a one-way input tape and Post tapes as storage tapes, which in the multihead version are scanned from left to right by a write head and several read heads. By simulating Post machines by multiple reset machines, and vice versa, several new characterisations of the class MULTI-RESET are obtained, and it is shown that for multihead and multitape Post machines linear time is no more powerful than real time, and two Post tapes or, alternatively, three heads on one Post tape are as powerful as any finite number of heads or tapes. Finally, some complexity bounds for equality sets and Post machines are discussed.     

Three-way two-dimensional alternating finite automata with rotated inputs

The authors have introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by three-way (deterministic and nondeterministic) finite automata, and have investigated the accepting powers. This paper continues the investigation of this type of automata, which consists of four three-way two-dimensional alternating finite automata (tr2-afa’s). We first investigate a relationship between the accepting powers of ∨-type automata (obtained by combining tr2-afa’s in ‘or’ fashion) and ∧-type automata (obtained by combining tr2-afa’s in ‘and’ fashion), and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-afa’s combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional nondeterministic and alternating finite automata.     

Cellular automata with limited inter-cell bandwidth

A d-dimensional cellular automaton is a d-dimensional grid of interconnected interacting finite automata. There are models with parallel and sequential input modes. In the latter case, the distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially. Often in the literature this model is referred to as an iterative array. In this paper, d-dimensional iterative arrays and one-dimensional cellular automata are investigated which operate in real and linear time and whose inter-cell communication bandwidth is restricted to some constant number of different messages independent of the number of states. It is known that even one-dimensional two-message iterative arrays accept rather complicated languages such as {a^p∣p prime} or {a²ⁿ∣n∈N} (H. Umeo, N. Kamikawa, Real-time generation of primes by a 1-bit-communication cellular automaton, Fund. Inform. 58 (2003) 421-435). Here, the computational capacity of d-dimensional iterative arrays with restricted communication is investigated and an infinite two-dimensional hierarchy with respect to dimensions and messages is shown. Furthermore, the computational capacity of the one-dimensional devices in question is compared with the power of two-way and one-way cellular automata with restricted communication. It turns out that the relations between iterative arrays and cellular automata are quite different from the relations in the unrestricted case. Additionally, an infinite strict message hierarchy for real-time two-way cellular automata is obtained as well as a very dense time hierarchy for k-message two-way cellular automata. Finally, the closure properties of one-dimensional iterative arrays with restricted communication are investigated and differences to the unrestricted case are shown as well.     

One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.     

Finite automata with multiplication

A finite automaton with multiplication (FAM) is a finite automaton with a register which is capable of holding any positive rational number. The register can be multiplied by any of a fixed number of rationals and can be tested for value 1. Closure properties and decision problems for various types of FAM's (e.g. two-way, one-way, nondeterministic, deterministic) are investigated. In particular, it is shown that the languages recognized by two-way deterministic FAM's are of tape complexity log n and time complexity n³. Some decision problems related to vector addition systems are also studied.     

Marker versus inkdot over three-dimensional patterns

A multi-marker automaton is a finite automaton which keeps marks as pebbles in the finite control, and cannot rewrite any input symbols but can make marks on its input with the restriction that only a bounded number of these marks can exist at any given time. An improvement of picture recognizability of the finite automaton is the reason why the multi-marker automaton was introduced. On the other hand, a multi-inkdot automaton is a conventional automaton capable of dropping an inkdot on a given input tape for a landmark, but unable to further pick it up. This paper deals with marker versus inkdot over threedimensional input tapes, and investigates some properties. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Undecidability of the first-order arithmetic A[P(x), 2x, x + 1]

It is shown that the first-order arithmetic A[P(x), 2x, x + 1] with two functions 2x, x + 1 and a monadic predicate symbol P(x) is undecidable, by using a kind of two-dimensional finite automata, called finite causal ω²-systems. From this immediately follows R.M. Robinson's result, which says that the monadic second-order theory with two functions 2x, x + 1 is undecidable. This is also considered as an improvement on H. Putnam's result about the undecidability of the first-order arithmetic with addition and a monadic predicate symbol.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

A communications system for irregular local interaction problems on a concurrent computer

The solution of a large class of problems requires the repeated evaluation of matrix vector products: y = Ax. An appropriate data decomposition and communications system to exchange x components among processors is necessary for efficient evaluation of these vector products on an MIMD concurrent computer. A communications system is presented for the case of a sparse matrix A that arises from a finite element or finite difference discretization of a partial differential equation on an irregular region, or from some kind of finite range interaction between particles. The method presented here uses a domain decomposition of the physical space to distribute A and x among processors. A packed form of the matrix is used which turns out to be very convenient to set up the data structures necessary to send and receive the extra x components. The resulting communications scheme has been used in a multigrid solver for finite element static elasticity problems and in a program which solves an eigenvalue problem. Speed up factors were determined on a 32 processor Caltech/JPL Mark II hypercube with good results. The communications system is not hypercube specific and can easily be implemented on other types of MIMD parallel computers.     

Hybrid numerical methods for convection-diffusion problems in arbitrary geometries

The hybrid nodal-integral/finite element method (NI-FEM) and the hybrid nodal-integral/finite analytic method (NI-FAM) are developed to solve the steady-state, two-dimensional convection-diffusion equation (CDE). The hybrid NI-FAM for the steady-state problem is then extended to solve the more general time-dependent, two-dimensional, CDE. These hybrid coarse mesh methods, unlike the conventional nodal-integral approach, are applicable in arbitrary geometries and maintain the high efficiency of the conventional nodal-integral method (NIM). In steady-state problems, the computational domain for both hybrid methods is discretized using rectangular nodes in the interior of the domain and along vertical and horizontal boundaries, while triangular nodes are used along the boundaries that are not parallel to the x or y axes. In time-dependent problems, the rectangular and triangular nodes become space-time parallelepiped and wedge-shaped nodes, respectively. The difference schemes for the variables on the interfaces of adjacent rectangular/parallelepiped nodes are developed using the conventional NIM. For the triangular nodes in the hybrid NI-FEM, a trial function is written in terms of the edge-averaged concentration of the three edges and made to satisfy the CDE in an integral sense. In the hybrid NI-FAM, the concentration over the triangular/wedge-shaped nodes is represented using a finite analytic approximation, which is based on the analytic solution of the one-dimensional CDE. The difference schemes for both hybrid methods are then developed for the interfaces between the rectangular/parallelepiped and triangular/wedge-shaped nodes by imposing continuity of the flux across the interfaces. A formal derivation of these hybrid methods and numerical results for several test problems are presented and discussed.     

The enumeration of permutations sortable by pop stacks in parallel

We show that the set of permutations sortable by k pop stacks in parallel has a regular insertion encoding and construct the (finite) recognizing automaton for this language. This shows that these permutations have a rational generating function, verifying a conjecture of Atkinson and Sack.     

Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors

By reducing an array matching problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms may be applied to arrays. In this paper, based on the ideas due to Baker, an application of the two-dimensional on-line tessellation acceptor (2-dota) is presented for very rapid on-line detection of occurrences of a fixed set of keyarrays as embedded subarrays in a text array. The main part of the algorithm described in this paper consists of constructing two finite state pattern (string) matching machines from the keyarrays. By combining these two finite state pattern matching machines, we construct the 2-dota which, given an m × n text array, solves the two-dimensional pattern matching problem in m + n?1 steps.     

On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ

In this paper,we first give a method that for any inverse finite automaton M' withdelay τ,all inver tible finite automata with delay τ,of which M' is an inverse with delayτ,can be constructed;and a universal nondeterministic finite automaton,for all finiteautomata of which M' is an inverse with delay τ,can also be constructed.We then give amethod that for any weak inverse finite automaton M' with delay τ,all weaklyinvertible finite automata with delay τ of which M' is a weak inverse with delay,can beconstructed;and a universal nondeterministic finite automaton,for all finiteautomata of which M' is a weak inverse with delay τ,can also be constructed.     

A power-set construction for reducing Büchi automata to non-determinism degree two

Büchi automata are finite automata that accept languages of infinitely long strings, so-called ω-languages. It is well known that, unlike in the finite-string case, deterministic and non-deterministic Büchi automata accept different ω-language classes, i.e., that determination of a non-deterministic Büchi automaton using the classical power-set construction will yield in general a deterministic Büchi automaton which accepts a superset of the ω-language accepted by the given non-deterministic automaton.In this paper, a power-set construction to a given Büchi automaton is presented, which reduces the degree of non-determinism of the automaton to at most two, meaning that to each state and input symbol, there exist at most two distinct successor states. The constructed Büchi automaton of non-determinism degree two and the given Büchi automaton of arbitrary non-determinism degree will accept the same ω-language.     

Der programmierbare endliche automat

Summary The paper deals with finite automata with two tapes, the second tape of which is interpreted as programme tape. For fixed automata those classes: of languages are considered, which can be accepted by variation of the programmes. The representation of all regular sets over some alphabet X by a fixed one-way automaton proves to be impossible. This problem has not yet been solved for automata with rewind instructions and two-way automata, which are strongly more powerful than one-way automata.

---

---

Diese Arbeit ist ein Auszug aus der Diplomarbeit, die von Prof. Dr. G. Hotz vergeben und betreut wurde. Ihm möchte der Verfasser seinen Dank aussprechen für das sehr interessante Thema.