Abstract We introduce and investigate tree-walking-storage automata, which are finite-state devices equipped with a tree-like storage. The automata are generalized stack automata, where the linear stack storage is replaced by a non-linear tree-like stack. Therefore, tree-walking-storage automata have the ability to explore the interior of the tree storage without altering the contents, where the possible moves of the tree pointer correspond to those of tree-walking automata. In addition, a tree-walking-storage automaton can append (push) non-existent descendants to a tree node and remove (pop) leaves from the tree. As for classical stack automata, we also consider non-erasing and checking variants. As a first step to investigate these models we consider the computational capacities of deterministic one-way variants. In particular, a primary focus lies on comparing the different variants of tree-walking-storage automata as well as with classical stack automata, enabling us to draw a complete picture. Basic closure properties of the induced families of languages are shown. In particular, we consider Boolean operations and several AFL operations.

The use of translucent input letters represents a way of implementing a discontinuous input processing in automata. In detail, a translucent automaton performs several sweeps from left to right on the input: according to the current state, some symbols are visible and can be processed, whereas some other symbols are invisible and may be processed in another sweep. We also distinguish between the returning and non-returning mode, which differ in the way the automaton behaves after reading a symbol: in the returning mode, a new sweep starts immediately, while in the non-returning mode, the device processes the next visible symbol. Here, we investigate deterministic pushdown automata with translucent letters both in the returning and non-returning mode. We prove that the non-returning mode strictly outperforms the returning mode, and that the families of the languages accepted by these two types of devices can be ranked strictly between the deterministic context-free languages and the deterministic context-sensitive languages. Moreover, both families are shown to be incomparable to the families of context-free, growing context-sensitive, and Church-Rosser languages. The ability of accepting non-semilinear languages is also emphasized (addressing an open question in the literature). Finally, we study the closure properties of both language families under the Boolean operations, obtaining that they are both closed under complementation but not under union and intersection. Further non-closure results are pointed-out for returning devices.

Abstract We study deterministic tree-walking-storage automata, which are finite-state devices equipped with a tree-like storage. These automata are generalized stack automata, where the linear stack storage is replaced by a non-linear tree-like stack. Therefore, tree-walking-storage automata have the ability to explore the interior of the tree storage without altering the contents, with the possible moves of the tree pointer corresponding to those of tree-walking automata. In addition, a tree-walking-storage automaton can append (push) non-existent descendants to a tree node and remove (pop) leaves from the tree. Here we are particularly considering the capacities of deterministic tree-walking-storage automata working in real time. It is shown that even the non-erasing variant can accept rather complicated unary languages as, for example, the language of words whose lengths are powers of two, or the language of words whose lengths are double Fibonacci numbers. Comparing the computational capacities with automata from the classical automata hierarchy, we derive that the family of languages accepted by real-time deterministic (non-erasing) tree-walking-storage automata is located between the regular and the deterministic context-sensitive languages. Moreover, the families are incomparable with the families of context-free and growing context-sensitive languages. It turns out that the devices under consideration accept unary languages in non-erasing mode that cannot be accepted by any classical stack automaton, even in erasing mode and arbitrary time. Basic closure properties of the induced families of languages are shown. In particular, we consider Boolean operations and AFL operations. It turns out that the two families in question have the same properties and, in particular, share all but one of these closure properties with the important family of deterministic context-free languages. Then, we consider the computational capacity of the counterpart to counter- and stack-counter automata, where the set of stack symbols is a singleton. Finally, we explore several decidability problems and show, that even for devices with a single tree symbol, the problems are all non-semidecidable by reductions of non-semidecidable problems of Turing machines.

Exclusive nondeterministic finite automata (XNFA) are nondeterministic finite automata with an exclusive-or-like acceptance condition. An input is accepted if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. It turns out that, from a descriptional complexity point of view, XNFAs differ significantly from the known types of finite automata. In particular the state costs for the simulation of an XNFA by a DFA are states, while the costs for simulating an XNFA by an NFA are states. Both bounds are also shown to be tight. On the other hand, NFAs may have advantages in comparison to XNFAs. For the simulation of an NFA by an XNFA, a tight bound of states is given. Finally, we investigate the computational complexity of different decision problems for XNFAs and it turns out that emptiness, universality, inclusion, and equivalence are PSPACE -complete.

Abstract String assembling systems are biologically inspired mechanisms that generate strings from copies out of finite sets of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction of assembly units that may appear at the beginning, during, or at the end of the assembling process and by a length restriction on the units. We investigate the power of these model-inherent control mechanisms by considering variants where one or more of these mechanisms are relaxed. The generative capacities and the relative power of the variants are our main interest. In particular, we prove that the power gained in the different control mechanisms may yield strictly more powerful systems and incomparable capacities. Additionally, we generalize these systems to multi-stranded systems. We obtain a strong connection to one-way multi-head finite automata and show an infinite, dense, and strict strand hierarchy. Finally, we examine the closure properties of the different variants of string assembling systems.

Input-driven pushdown automata (IDPDAs) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the input symbol. Nowadays such devices are usually defined such that every push operation pushes exactly one additional symbol on the pushdown store and, in addition, stationary moves are not allowed so that the devices work in real time. Here, we relax this strong definition and consider IDPDAs that may push more than one symbol in one step (push-IDPDA) or may perform stationary moves (stat-IDPDA). We study the computational power of the extended variants both in the deterministic and nondeterministic case, we investigate several decidability questions for the new automata classes, and we obtain interesting representations by inverse homomorphisms. Namely, every (1) deterministic, (2) real-time deterministic, and (3) nondeterministic context-free language can be characterized as the inverse homomorphic image of a language accepted by a (1) stat-IDPDA, (2) push-IDPDA, and (3) nondeterministic push-IDPDA.

An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. All sweeps always start from the sole initial state. The device accepts upon halting in an accepting state at the end of a sweep. We consider devices with one-way sweep motion and two-way sweep motion, i.e., sweeps are either from left to right only, or strictly alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. We focus on iterated uniform finite-state transducers accepting unary languages, i.e., languages built over single-letter alphabets. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max⁡{2⋅ϱ,p}+1 states, where ϱ and p are the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. Such a state cost cannot be improved by using two-way motion, and it turns out to greatly outperform in the worst case the state costs of equivalent classical models of finite-state automata. Next, we give a characterization of classes of unary languages accepted by non-constant sweep-bounded iterated uniform finite-state transducers in terms of time-bounded one-way cellular automata. This characterization enables both to exhibit interesting families of unary nonregular languages accepted by iterated uniform finite-state transducers, and to prove the undecidability of several questions related to iterated uniform finite-state transducers accepting unary languages with an amount of sweeps that is at least logarithmic.

Abstract We investigate finite automata whose state graphs are undirected. This means that for any transition from state p to q consuming some letter a from the input there exists a symmetric transition from state q to p consuming a letter a as well. So, the corresponding language families are subregular, and in particular in the deterministic case, subreversible. In detail, we study the operational descriptional complexity of deterministic and nondeterministic undirected finite automata. To this end, the different types of automata on alphabets with few letters are characterized. Then, the operational state complexity of the Boolean operations as well as the operations concatenation and iteration is investigated, where tight upper and lower bounds are derived for unary as well as arbitrary alphabets under the condition that the corresponding language classes are closed under the operation considered.

An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTss are "one-way" devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace(lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.

Abstract We study the computational capacity of self-verifying iterative arrays ( $${\text {SVIA}}$$ SVIA ). A self-verifying device is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. It turns out that, for any time-computable time complexity, the family of languages accepted by $${\text {SVIA}}$$ SVIA s is a characterization of the so-called complementation kernel of nondeterministic iterative array languages, that is, languages accepted by such devices whose complementation is also accepted by such devices. $${\text {SVIA}}$$ SVIA s can be sped-up by any constant multiplicative factor as long as the result does not fall below realtime. We show that even realtime $${\text {SVIA}}$$ SVIA are as powerful as lineartime self-verifying cellular automata and vice versa. So they are strictly more powerful than the deterministic devices. Closure properties and various decidability problems are considered.

Abstract Iterative arrays whose internal inter-cell communication is quantitatively restricted are investigated. The quantity of communication is measured by counting the number of uses of the links between cells. In particular, iterative arrays are studied where the maximum number of communications per cell occurring in accepting computations is drastically bounded by a constant number. Additionally, the iterative arrays have to work in realtime. We study the computational capacity of such devices. For example, a result is that a strict and dense hierarchy with respect to the constant number of communications exists. Due to their very restricted communication, the question arises whether the usually studied decidability problems such as, for example, emptiness, finiteness, inclusion, or equivalence become decidable for such devices. However, it can be shown that all such decidability questions remain undecidable even if only four communications per cell are allowed. Finally, the undecidability results are shown to hold as well for one-way and two-way cellular automata having at most four communications per cell.

Abstract To determine the computational capacity of cellular automata they are often investigated towards their ability to accept formal languages within certain time constraints. In this paper, we take up an opposite position and look at cellular automata towards their ability to generate patterns, within certain time constraints. As an example we describe a construction of a cellular automaton that generates prefixes of the Oldenburger–Kolakoski sequence within real time. Furthermore, we study the real-time generation of unary and non-unary patterns in depth. In the unary case, we obtain a characterization by time-constructible functions and their corresponding unary formal languages. In the non-unary case, we provide constructions that generate any arbitrary given properly thin context-free language as well as all prefixes of any given automatic sequence.

We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.

A two-sided extension of strictly locally testable languages is presented. In order to determine membership within a two-sided strictly locally testable language, the input must be scanned from both ends simultaneously, whereby it is synchronously checked that the factors read are correlated with respect to a given binary relation. The class of two-sided strictly locally testable languages is shown to be a proper subclass of the even linear languages that is incomparable to the regular languages with respect to inclusion. Furthermore, closure properties of the class of two-sided strictly locally testable languages and decision problems are studied. Finally, it is shown that two-sided strictly k-testable languages are learnable in the limit from positive data.

In input-driven automata the input alphabet is divided into distinct classes and different actions on the storage medium are solely governed by the input symbols. For example, in input-driven pushdown automata (IDPDA) there are three distinct classes of input symbols determining the action of pushi ng, popping, or doing nothing on the pushdown store. Here, input-driven automata are extended in such a way that the input is preprocessed by a deterministic sequential transducer. IDPDAs extended in this way are called tinput-driven pushdown automata (TDPDA) and it turns out that TDPDAs are more powerful than IDPDAs but still not as powerful as real-time deterministic pushdown automata. Nevertheless, even this stronger model has still good closure and decidability properties. In detail, it is shown that TDPDAs are closed under the Boolean operations union, intersection, and complementation. Furthermore, decidability procedures for the inclusion problem as well as for the questions of whether a given automaton is a TDPDA or an IDPDA are developed. Additionally, representation theorems for the context-free languages using IDPDAs and TDPDAs are established. Two other classes investigated are on the one hand TDPDAs restricted to tinput-driven counter automata and on the other hand TDPDAs generalized to tinput-driven stack automata. In both cases, it is possible to preserve the good closure and decidability properties of TDPDAs, namely, the closure under the Boolean operations as well as the decidability of the inclusion problem.

A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where k ≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform rev ersible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all k ≥ 0, sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and k + 3 rewrite operations. We investigate closure properties of the family of languages accepted by reversible k-limited automata. It turns out that these families are not closed under intersection, but are closed under complementation. They are closed under intersection with regular languages, which leads to the non-closure under concatenation, iteration, and homomorphisms. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

Deterministic finite automata equipped with the storage medium of a queue are investigated towards their ability to perform reversible computations, that is, computations in which every occurring configuration has exactly one successor and exactly one predecessor. A first result is that any queue a utomaton can be simulated by a reversible one. So, reversible queue automata are as powerful as Turing machines. Therefore it is of natural interest to impose time restrictions to queue automata. Here we consider quasi realtime and realtime computations. It is shown that every reversible quasi realtime queue automaton can be sped up to realtime. On the other hand, under realtime conditions reversible queue automata are less powerful than general queue automata. Furthermore, we exhibit a lower bound of Ω(n2log(n)) time steps for realtime queue automata witness languages to be accepted by any equivalent reversible queue automaton. We study the closure properties of reversible realtime queue automata and obtain similar results as for reversible deterministic pushdown automata. Finally, we investigate decidability questions and obtain that all commonly studied questions such as emptiness, finiteness, or equivalence are not semidecidable for reversible realtime queue automata. Furthermore, it is not semidecidable whether an arbitrary given realtime queue automaton is reversible.

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on th

The parallel models of cellular automata and iterative arrays are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time al

Many non-classical automata models are natural objects of theoretical computer science.They are studied from different points of view in various areas, both as theoretical concepts and as formal models for applications.A deeper and interdisciplinary coverage of this particular area may lead to new insights and substantial progress.The Second Workshop on Non-Classical Models of Automata and Applications (NCMA 2010) has been organized in order to bring together researchers working on different aspects of various variants of non-classical automata models to exchange and develop novel ideas.

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

A not so well-known result in formal language theory is that the Higman-Haines sets for any language are regular [11, Theorem 4.4]. It is easily seen that these sets cannot be effectively computed in general. The Higman-Haines sets are the languages of all scattered subwords of a given language as well as the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines sets was studied in [8]. Here we focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of descriptions of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the family of regular, linear context-free, and context-free languages. We prove upper and lower bounds on the size of descriptions of these sets for general and unary languages.

Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the well­known result that each tally language acceptable by a classical one­way cellular automaton (OCA) in real­time has to be a regular language we will answer the three natural questions 'How much time do we have to provide?' 'How much power do we have to plug in the single cells (i.e., how complex has a single cell to be)?' and 'How can we modify the mode of operation (i.e., how much nondeterminism do we have to add)?' in order to accept non­regular tally languages. We show the surprising result that for some classes of generalized interacting automata parallelism does not lead to more accepting power than obtained by a single sequential cell. Adding a wee bit of nondeterminism an infinite hierarchy of unary language families can be shown by allowing more and more nondeterminism.