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.

The research on distributed computing by robot swarms has formalized different models where robots act through a sequence of Look-Compute-Move cycles in the Euclidean plane. Models mostly under study differ for (i) the possibility of storing constant-size information, (ii) the possibility of communicating constant-size information, (iii) the synchronization mode, and (iv) the visibility of robots. By varying features (i) and (ii) , we obtain the noted four base models: OBLOT (silent and oblivious robots), FSTA (silent and finite-state robots), FCOM (oblivious and finite-communication robots), and LUMI (finite-state and finite-communication robots). Feature (iii) comprehends the three main synchronization modes: fully synchronous , semi-synchronous , and asynchronous . According to robot visibility (iv) , models can assume robots to be transparent (thus enjoying complete visibility ) or opaque (thus experiencing obstructed visibility in case of collinearities). By combining features (i-iv) , we obtain 24 models. Extensive research has studied the computational power of the 12 transparent models, proving the hierarchical relations among them; to this regard, it is worth noticing that robots have been assumed to be collision-tolerant. In this work, we assume our robots to be collision-intolerant and we lay down the computational hierarchy by considering all 24 models. Firstly, we study the relations between the transparent and the opaque framework, focusing on how obstructed visibility affects the computational power of a model. Then, we introduce five witness problems that prove most of the computational relations among the 24 models. • We consider 24 robot models differing in memory, communication, synchronization, and visibility (transparent vs. opaque). • Some problems are exhibited, which cannot be solved under any opaque model. • Five witness problems are designed, showing the dominance and orthogonality relations among the models. • We introduce the phenomenon of “false election” occurring in case of asynchronism and obstructed visibility. • We provide an almost complete relation table depicting the computational hierarchy of the 24 models under study.

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.

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 consider the notion of a constant length queue automaton—i.e., a traditional queue automaton with a built-in constant limit on the length of its queue—as a formalism for representing regular languages. We show that the descriptional power of constant length queue automata greatly outperforms that of traditional finite state automata, of constant height pushdown automata, and of straight line programs for regular expressions, by providing optimal exponential and double-exponential size gaps. Moreover, we prove that constant height pushdown automata can be simulated by constant length queue automata paying only by a linear size increase, and that removing nondeterminism in constant length queue automata requires an optimal exponential size blow-up, against the optimal double-exponential cost for determinizing constant height pushdown automata. Finally, we investigate the size cost of implementing Boolean language operations on deterministic and nondeterministic constant length queue automata.

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.

We show that, for any ϵ > 0, there exists a language accepted in strong ϵ log n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e.,

We consider the problem of computing the costs---{ in terms of states---of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary n-state two-way nondeterministic automata by $O({{\rm e}^{\sqrt{{n}\ln{n}}}})$-state one-way deterministic automata. In addition, we show that, given a unary n-state two-way nondeterministic automaton, one can construct an equivalent O(n 2 )-state two-way nondeterministic automaton performing both input head reversals and nondeterministic choices only at the ends of the input tape. Further results on simulating unary one-way alternating finite automata are also discussed.

The complexity measure under consideration is $\mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS}$ for Turing machines that are able to branch both existentially and universally. We show that, for any function $h(n)$ between $\log\log n$ and $\log n$, $\Pi_1 \mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS} (h(n))$ is separated {}from $\Sigma_1 \mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS} (h(n))$ as well as {}from $\mbox{\sf co}\Sigma_1 \mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS} (h(n))$, for middle, accept, and weak modes of this complexity measure. This also separates determinism from the higher levels of the alternating hierarchy. For "well-behaved" functions h(n) between log log n and log n, almost all of the above separations can be obtained by using unary witness languages. In addition, the construction of separating languages contributes to the research on minimal resource requirements for computational devices capable of recognizing nonregular languages. For any (arbitrarily slow growing) unbounded monotone recursive function f(n), a nonregular unary language is presented that can be accepted by a \middle\ \mbox{$\Pi_1$ alternating} Turing machine in s(n) space and i(n) input head reversals, with $s(n)\cdot i(n)\in{\cal O}(\log\log n\cdot f(n))$. Thus, there is no exponential gap for the optimal lower bound on the product $s(n)\cdot i(n)$ between unary and general nonregular language acceptance---in sharp contrast with the one-way case.