International Journal of Foundations of Computer Science

A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word $w\in {\{a,b\}}^{\ast }$ can be reconstructed from the number of occurrences of at most $min(|w{|}_a,|w{|}_b)+1$ scattered factors of the form $a^{i}b$, where $|w{|}_a$ is the number of occurrences of the letter $a$ in $w$. Moreover, we generalise the result to alphabets of the form $\{1,\dots ,q\}$ by showing that at most ${\sum }_{i=1}^{q-1}|w{|}_i(q-i+1)$ scattered factors suffices to reconstruct $w$. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.

For a formal language $L$, the problem of language enumeration asks to compute the length-lexicographically smallest word in $L$ larger than a given input $w\in {\mathrm{\Sigma }}^{\ast }$ (henceforth called the $L$-successor of $w$). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if $L$ is recognized by a DFA with $n$ states, then $2^{\mathrm{\Theta }(\sqrt{nlogn})}$ states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute $L$-successors. As a byproduct, we obtain that if $L$ is recognized by a DFA with $n$ states, then $2^{\mathrm{\Theta }(\sqrt{nlogn})}$ states are sufficient for a DFA to recognize the subset $S(L)$ of $L$ composed of its lexicographically smallest words. We give a matching lower bound that holds even if $S(L)$ is represented as an NFA. It has been known that $L$-successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in $NL$. If the regular language $L$ is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of $L$ under $DLOGTIME$-uniform ${AC}^0$ reductions. In particular, this implies that fixed star-free languages can be enumerated in ${AC}^0$, arbitrary fixed regular languages can be enumerated in ${NC}^1$ and that there exist regular languages for which the problem is ${NC}^1$-complete.

We consider the range of possible dynamics of cellular automata (CA) on two-sided beta-shifts $S_{\beta }$ and its relation to direct topological factorizations. We show that any reversible CA $F:S_{\beta }\to S_{\beta }$ has an almost equicontinuous direction whenever $S_{\beta }$ is not sofic. This has the corollary that non-sofic beta-shifts are topologically direct prime, i.e. they are not conjugate to direct topological factorizations $X\times Y$ of two nontrivial subshifts $X$ and $Y$. We also give a simple criterion to determine whether $S_{n\gamma }$ is conjugate to $S_n\times S_{\gamma }$ for a given integer $n\ge 1$ and a given real $\gamma >1$ when $S_{\gamma }$ is a subshift of finite type. When $S_{\gamma }$ is strictly sofic, we show that such a conjugacy is not possible at least when $\gamma$ is a quadratic Pisot number of degree $2$. We conclude by using direct factorizations to give a new proof for the classification of reversible multiplication automata on beta-shifts with integral base and ask whether nontrivial multiplication automata exist when the base is not an integer.

Splicing systems are generative mechanisms introduced by Tom Head in 1987 to model the biological process of DNA recombination. The computational engine of a splicing system is the “splicing operation”, a cut-and-paste binary string operation defined by a set of “splicing rules”, quadruples $r=(u_1,u_2;u_3,u_4)$ where $u_1,u_2,u_3,u_4$ are words over an alphabet $\mathrm{\Sigma }$. For two strings $x_1{u}_1{u}_2{y}_1$ and $x_2{u}_3{u}_4{y}_2$, applying the splicing rule $r$ produces the string $x_1{u}_1{u}_4{y}_2$. In this paper we focus on a particular type of splicing systems, called $(i,j)$ semi-simple splicing systems, $i=1,2$ and $j=3,4$, wherein all splicing rules $r$ have the property that the two strings in positions $i$ and $j$ in $r$ are singleton letters, while the other two strings are empty. The language generated by such a system consists of the set of words that are obtained starting from an initial set called “axiom set”, by iteratively applying the splicing rules to strings in the axiom set as well as to intermediately produced strings. We consider semi-simple splicing systems where the axiom set is a regular language, and investigate the descriptional complexity of such systems in terms of the size of the minimal deterministic finite automata that recognize the languages they generate.

After an apparent hiatus of roughly 30 years, we revisit a seemingly neglected subject in the theory of (one-dimensional) cellular automata: sublinear-time computation. The model considered is that of ACAs, which are language acceptors whose acceptance condition depends on the states of all cells in the automaton. We prove a time hierarchy theorem for sublinear-time ACA classes, analyze their intersection with the regular languages, and, finally, establish strict inclusions in the parallel computation classes $SC$ and (uniform) $AC$. As an addendum, we introduce and investigate the concept of a decider ACA (DACA) as a candidate for a decider counterpart to (acceptor) ACAs. We show the class of languages decidable in constant time by DACAs equals the locally testable languages, and we also determine $\mathrm{\Omega }(\sqrt{n})$ as the (tight) time complexity threshold for DACAs up to which no advantage compared to constant time is possible.

In this article, we study the impact of applying simple reduction rules to random syntactic formulas encoded as trees. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with $n$ nodes, then the expected size of the result is bounded by a constant. The same holds for higher moments, establishing the lack of expressivity of uniform random expressions. Our framework is quite general as we consider expressions defined by systems of combinatorial equations. For our proofs, we rely on Drmota’s multidimensional theorem for systems of generating functions.

A language over an alphabet $\mathsf{B}=\mathsf{A}\cup \overline{\mathsf{A}}$ of opening ($\mathsf{A}$) and closing ($\overline{\mathsf{A}}$) brackets, is balanced if it is a subset of the Dyck language ${𝔻}_{\mathsf{B}}$ over $\mathsf{B}$, and it is well-formed if all words are prefixes of words in ${𝔻}_{\mathsf{B}}$. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-$\mathsf{TW}$ of non-linear tree transducers with output alphabet $\mathsf{B}$ whether or not the output language is balanced.

Results in $C^{\ast }$ algebras, of Matte Bon and Le Boudec, and of Haagerup and Olesen, apply to the R. Thompson groups $F\le T\le V$. These results together show that $F$ is non-amenable if and only if $T$ has a simple reduced $C^{\ast }$-algebra.

In further investigations into the structure of $C^{\ast }$-algebras, Breuillard, Kalantar, Kennedy, and Ozawa introduce the notion of a normalish subgroup of a group $G$. They show that if a group $G$ admits no non-trivial finite normal subgroups and no normalish amenable subgroups then it has a simple reduced $C^{\ast }$-algebra. Our chief result concerns the R. Thompson groups $F<T<V$; we show that there is an elementary amenable group $E<F$ [where here, $E\cong \dots )\wr \mathbb{Z})\wr \mathbb{Z})\wr \mathbb{Z}$] with $E$ normalish in $V$.

The proof given uses a natural partial action of the group $V$ on a regular language determined by a synchronising automaton in order to verify a certain stability condition: once again highlighting the existence of interesting intersections of the theory of $V$ with various forms of formal language theory.

This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automaton (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves like a linear function, or it can not be bounded by any function of the length of the input word (and it is decidable which case occurs). However, this result does not hold for non-erasing stack automata; we provide an example where the space complexity grows proportionally to the square root of the length of the input. Furthermore, we study the complexity bounds of machines which accept a given language, and decidability of space complexity properties.