International Journal of Foundations of Computer Science

We consider tissue P systems working on vesicles of multisets with the very simple operations of insertion, deletion, and substitution of single objects. With the whole multiset being enclosed in a vesicle, sending it to a target cell can be indicated in those simple rules working on the multiset. As derivation modes we consider the sequential derivation mode, where, if possible, one rule is applied in a derivation step, and the set maximally parallel derivation mode, where in each derivation step a non-extendable set of rules indicating the same target cell is applied. With the set maximally parallel derivation mode, computational completeness can already be obtained with tissue P systems having a tree structure, whereas tissue P systems even with an arbitrary communication structure are not computationally complete when working in the sequential mode. Adding polarizations — only the three polarizations $-1$, $0$, $1$ are sufficient — allows for obtaining computational completeness even for tissue P systems working in the sequential mode.

We use results on Dyck words and lattice paths to derive a formula for the exact number of binary words of a given length with a given minimal abelian border length, tightening a bound on that number from Christodoulakis et al. (Discrete Applied Mathematics, 2014). We extend to any number of distinct abelian borders a result of Rampersad et al. (Developments in Language Theory, 2013) on the exact number of binary words of a given length with no abelian borders. We also generalize these results to partial words.

Let $S$ be a complete star-omega semiring and $\mathrm{\Sigma }$ be an alphabet. For a weighted $\omega$-pushdown automaton ${𝒫}$ with stateset $\{1,\dots ,n\}$, $n\ge 1$, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair $({(S〈〈{\mathrm{\Sigma }}^{\ast }〉〉)}^{n\times n},{(S〈〈{\mathrm{\Sigma }}^{\omega }〉〉)}^n)$ such that the behavior $\parallel {𝒫}\parallel$ of ${𝒫}$ is a component of a solution of this system. In case the basic semiring is $𝔹$ or ${\mathbb{N}}^{\infty }$ we show that there exists a mixed context-free grammar that generates $\parallel {𝒫}\parallel$. The construction of the mixed context-free grammar from ${𝒫}$ is a generalization of the well known triple construction and is called now triple-pair construction for $\omega$-pushdown automata.

Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minimal reversible automaton recognizing a given language is not necessarily unique, moreover, there are languages having arbitrarily large reversible recognizers possessing no nontrivial “reversible” congruence. Building atop on our earlier result, we show that the corresponding decision problem is $NL$-complete, and that even in the case when there are only finitely many such reversible recognizers, the largest one among them can be exponentially larger than the minimal automaton. Both results hold for the case of binary alphabets.

Finite automata whose computations can be reversed, at any point, by knowing the last $k$ symbols read from the input, for a fixed $k$, are considered. These devices and their accepted languages are called $k$-reversible automata and $k$-reversible languages, respectively. The existence of $k$-reversible languages which are not $(k-1)$-reversible is known, for each $k>1$. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are $k$-reversible for some $k$. Conditions characterizing the class of $k$-reversible languages, for each fixed $k$, and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not $k$-reversible, but which accepts a $k$-reversible language, into an equivalent $k$-reversible finite automaton, is presented.

We introduce and study input-driven deterministic and nondeterministic double-head pushdown automata. A double-head pushdown automaton is a slight generalization of an ordinary pushdown automaton working with two input heads that move in opposite directions on the common input tape. In every step one head is moved and the automaton decides on acceptance if the heads meet. Demanding the automaton to work input-driven it is required that every input symbol uniquely defines the action on the pushdown store (push, pop, state change). Normally this is modeled by a partition of the input alphabet and is called a signature. Since our automaton model works with two heads either both heads respect the same signature or each head owes its own signature. This results in two variants of input-driven double-head pushdown automata. The induced language families on input-driven double-head pushdown automata are studied from the perspectives of their language describing capability, their closure properties, and decision problems.

Unary self-verifying symmetric difference automata have a known tight bound of $2^{n-1}-1$ for their state complexity. We now consider the non-unary case and show that, for every $n\ge 2$, there is a regular language ${{ℒ}}_n$ accepted by a non-unary self-verifying symmetric difference nondeterministic automaton with $n$ states, such that its equivalent minimal deterministic finite automaton has $2^{n-1}$ states. Furthermore, given any SV-XNFA with $n$ states, it is possible, up to isomorphism, to find at most another $|GL(n,{\mathbb{Z}}_2)|-1$ equivalent SV-XNFA. Finally, we show that for a certain set of non-unary SV-XNFA, $2^{n-1}$ is a tight bound on the state complexity.

The $\mathcal{ℒ}(PSCG)=\mathcal{ℒ}(CS)$ problem asks whether propagating scattered context grammars and context sensitive grammars are equivalent. The presented paper reformulates and answers this problem in terms of CD grammar systems. More specifically, it characterizes the family of context sensitive languages by two-component CD grammar systems with propagating scattered context rules.

We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic $k$-counter automata. Then, we show that exact realtime affine counter automata can recognize a family of regular languages with a few states but the states required by realtime deterministic $k$-counter automata cannot be bounded. We also show that stateless affine increment-only counter automata can recognize some nonregular languages with one-sided bounded-error. Moreover, we show that a promise problem not solved by two-way quantum finite automata in polynomial time can be solved by Las Vegas affine finite automata. Lastly, we present an affine finite automaton algorithm using a counter cleverly to recognize a language, for which we do not know any bounded-error affine finite automata or two-way quantum finite automata recognizing it.

Here we establish and study some rigorous tools suitable for the lexicalized syntactic analysis (LSA) of natural and formal languages. Motivated by the linguistic method of analysis by reduction, we are interested in correctness preserving LSA. We introduce a suitable model of automata, the h-lexicalized one-way restarting automata (h-RRWW), and compare the properties of their input languages, which are the languages considered traditionally in automata theory, to the properties of the so-called basic and h-proper languages. These languages form the basic components for LSA.

With respect to their input languages, h-RRWW-automata are not sensitive to the size of the read/write window and they allow computations that are far from being correctness preserving. On the other hand, for their basic and h-proper languages, h-RRWW-automata ensure that the resulting computations are completely correctness preserving, and they yield infinite ascending hierarchies of language classes within the regular, the context-free, and the context-sensitive languages that are based on the size of the read/write window.