International Journal of Foundations of Computer Science

In this article, we study some properties of random regular expressions of size $n$, when the cardinality of the alphabet also depends on $n$. For this, we revisit and improve the classical Transfer Theorem from the field of analytic combinatorics. This provides precise estimations for the number of regular expressions, the probability of recognizing the empty word and the expected number of Kleene stars in a random expression. For all these statistics, we show that there is a threshold when the size of the alphabet approaches $n^2$, at which point the leading term in the asymptotics starts oscillating.

For a regular language $L$, let $\mathrm{\text{Var}}(L)$ be the minimal number of nonterminals necessary to generate $L$ by right linear grammars. Moreover, for natural numbers $k_1,k_2,\dots ,k_n$ and an $n$-ary regularity preserving operation $f$, let the range $g_f^{\mathrm{\text{Var}}}(k_1,k_2,\dots ,k_n)$ be the set of all numbers $k$ such that there are regular languages $L_1,L_2,\dots ,L_n$ with $\mathrm{\text{Var}}(L_i)=k_i$ for $1\le i\le n$ and $\mathrm{\text{Var}}(f(L_1,L_2,\dots ,L_n))=k$. We show that, for the circular shift operation $\mathrm{\text{Circ}}$, $g_{\mathrm{\text{Circ}}}^{\mathrm{\text{Var}}}(n)$ is infinite for all $n$, and we completely determine the set $g_{\mathrm{\text{Circ}}}^{\mathrm{\text{Var}}}(2)$. Moreover, we give a precise range for the left right quotient and a partial result for the left quotient. Furthermore, we add some values to the range for the operation intersection which improves the result of [].

We consider the problem of partitioning effectively a given irreflexive (and possibly symmetric) rational relation $R$ into two asymmetric rational relations. This problem is motivated by a recent method of embedding an $R$-independent language into one that is maximal $R$-independent, where the method requires to use an asymmetric partition of $R$. We solve the problem when $R$ is length-separable, which means that the following two subsets of $R$ are rational: the subset of word pairs $(u,v)$ where $\left|u\right|\le \left|v\right|$; and the subset of word pairs $(u,v)$ where $\left|u\right|\ge \left|v\right|$. This property is satisfied by all recognizable, all left synchronous, and all right synchronous relations. We leave it as an open problem when $R$ is not length-separable. We also define zero-avoiding transducers for length-separable relations, which makes our partitioning solution constructive.

We examine different generalizations of checking stack automata by allowing multiple input heads and multiple stacks, and characterize their computing power in terms of two-way multi-head finite automata and space-bounded Turing machines. For various models, we obtain hierarchies in terms of their computing power. Our characterizations and hierarchies expand or tighten some previously known results. We also discuss some decidability questions and the space/time complexity of the models.

The $k$-prefix-free, $k$-suffix-free and $k$-infix-free languages generalize the prefix-free, suffix-free and infix-free languages by allowing marginal errors. For example, a string $x$ in a $k$-prefix-free language $L$ can be a prefix of up to $k$ different strings in $L$. We also define finitely prefix-free languages in which a string $x$ can be a prefix of finitely many strings. We present efficient algorithms that determine whether or not a given regular language is $k$-prefix-free, $k$-suffix-free or $k$-infix-free, and analyze the time complexity of the algorithms. We establish undecidability results for deciding these properties for (linear) context-free languages.

We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence or preorder relation and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences and preorders. We, in particular, show that computing equivalence and preorder relation from the left is more useful than the right for reducing the degree of nondeterminism in NFAs. We also present experimental evidence for showing that NFA reduction from the left achieves the better reduction of nondeterminism than reduction from the right.

Union-free expressions are regular expressions without using the union operation. Consequently, (nondeterministic) union-free languages are described by regular expressions using only concatenation and Kleene star. The language class is also characterised by a special class of finite automata: 1CFPAs have exactly one cycle-free accepting path from each of their states. Obviously such an automaton has exactly one accepting state. The deterministic counterpart of such class of automata defines the deterministic union-free (d-union-free, for short) languages. In this paper $\lambda$-free nondeterministic variants of 1CFPAs are used to define n-union-free languages. The defined language class is shown to be properly between the classes of (nondeterministic) union-free and d-union-free languages (in case of at least binary alphabet). In case of unary alphabet the class of n-union-free languages coincides with the class of union-free languages. Some properties of the new subregular class of languages are discussed, e.g., closure properties. On the other hand, a regular expression is in union normal form if it is a finite union of union-free expressions. It is well known that every regular expression can be written in union normal form, i.e., all regular languages can be described as finite unions of (nondeterministic) union-free languages. It is also known that the same fact does not hold for deterministic union-free languages, that is, there are regular languages that cannot be written as finite unions of d-union-free languages. As an important result here we show that every regular language can be defined by a finite union of n-union-free languages. This fact also allows to define n-union-complexity of regular languages.

Oritatami is a computational model of RNA cotranscriptional folding, in which an RNA transcript is folding upon itself while being synthesized from its template DNA. This model is known to be Turing universal. Under the restriction on its parameters delay and arity both being 1, however, any deterministically foldable conformation is known to be at most ten times as large as its initial conformation (seed), and hence, the model becomes weaker. In this paper, we shall improve the size upper bound from $10n$ down to $4n+5$ and also provide a system that can fold into a conformation of size $3n-20$. These tighter bounds result from a novel graph representation of deterministic oritatami folding pathways. We shall also study the case in which a transcript is trapped in a region closed by a seed and show that under this confinement, the upper bound is further improved to $\frac{11}{3}n-5$.

We prove an inequality for the number of periods in a word $x$ in terms of the length of $x$ and its initial critical exponent. Next, we characterize all periods of the length-$n$ prefix of a characteristic Sturmian word in terms of the lazy Ostrowski representation of $n$, and use this result to show that our inequality is tight for infinitely many words $x$. We propose two related measures of periodicity for infinite words. Finally, we also consider special cases where $x$ is overlap-free or squarefree.