Narrow Results

A class of languages is closed under a given operation if the resulting language belongs to this class whenever the operands belong to it. We examine the closure properties of various subclasses of regular languages under basic operations of intersection, union, concatenation and power, positive closure and star, reversal, and complementation. We consider the following classes: definite languages and their variants (left ideal, finitely generated left ideal, symmetric definite, generalized definite and combinational), two-sided comets and their variants comets and stars, and the classes of singleton, finite, ordered, star-free, and power-separating languages. We also give an overview about subclasses of convex languages (classes of ideal, free, and closed languages), union-free languages, and group languages. We summarize some inclusion relations between these classes. Subsequently, for all pairs of a class and an operation, we provide an answer whether this class is closed under this operation or not.

While the closure of a language family $\mathcal{ℒ}$ under certain language operations is the least family of languages which contains all members of $\mathcal{ℒ}$ and is closed under all of the operations, a kernel of $\mathcal{ℒ}$ is a maximal family of languages which is a sub-family of $\mathcal{ℒ}$ and is closed under all of the operations. Here we investigate properties of kernels of general language families and operations defined thereon as well as kernels of (deterministic) (linear) context-free languages with a focus on Boolean operations. While the closures of language families are unique, this uniqueness is not obvious for kernels. We consider properties of language families and of operations that yield unique and non-unique, i.e. a set, of kernels. For the latter case, the question whether the union of all kernels coincides with the language family, or whether there are languages that do not belong to any kernel is addressed. Additionally, languages that are mandatory for each (Boolean) kernel and languages that are optional for (Boolean) kernels are studied. That is, we consider the intersection of all Boolean kernels as well as their union. The expressive capacities of these families are addressed leading to a hierarchical structure. Further closure properties are considered. Furthermore, we study descriptional complexity aspects of these families, where languages are represented by context-free grammars with proofs attached. It turns out that the size trade-offs between all families in question and deterministic context-free languages 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 latter system to the former.

Restarting automata were introduced by Jančar et al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we only require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class to the class . Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

This work is a continuation of the investigation started in [12], where a new-old type of control on context-free grammars is considered. This type of control is extracted and abstracted from a paper ([2]) with very solid linguistic motivations. The goal of this paper is to complete the picture of path-controlled grammars started in [12] with some mathematical properties which are missing from the aforementioned work: closure and decidability properties, including a polynomial recognition algorithm.

It is proved that the language family generated by Boolean grammars is effectively closed under injective gsm mappings and inverse gsm mappings (where gsm stands for a generalized sequential machine). The same results hold for conjunctive grammars, unambiguous Boolean grammars and unambiguous conjunctive grammars.

We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages accepted by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.

Hyper-minimization of deterministic finite automata (DFA) is a recently introduced state reduction technique that allows a finite change in the recognized language. A generalization of this lossy compression method to the weighted setting over semifields is presented, which allows the recognized weighted language to differ for finitely many input strings. First, the structure of hyper-minimal deterministic weighted finite automata is characterized in a similar way as in classical weighted minimization and unweighted hyper-minimization. Second, an efficient hyper-minimization algorithm, which runs in time , is derived from this characterization. Third, the closure properties of canonical regular languages, which are languages recognized by hyper-minimal DFA, are investigated. Finally, some recent results in the area of hyper-minimization are recalled.

The paper characterizes the family of homomorphisms, under which the deterministic context-free languages, the LL context-free languages and the unambiguous context-free languages are closed. The family of deterministic context-free languages is closed under a homomorphism h if and only if h is either a code of bounded deciphering delay, or the images of all symbols under h are powers of the same string. The same characterization holds for LL context-free languages. The unambiguous context-free languages are closed under h if and only if either h is a code, or the images of all symbols under h are powers of the same string.

The notion of a $k$-automatic set of integers is well-studied. We develop a new notion — the $k$-automatic set of rational numbers — and prove basic properties of these sets, including closure properties and decidability.

We consider the model of deterministic set automata which are basically deterministic finite automata equipped with a set as an additional storage medium. The basic operations on the set are the insertion of elements, the removing of elements, and the test whether an element is in the set. We investigate the computational power of deterministic set automata and compare the language class accepted with the context-free languages and classes of languages accepted by queue automata. As result the incomparability to all classes considered is obtained. Furthermore, we examine the closure properties under several operations. Then we show that deterministic set automata may be an interesting model from a practical point of view by proving that their regularity problem as well as the problems of emptiness, finiteness, infiniteness, and universality are decidable. Finally, the descriptional complexity of deterministic and nondeterministic set automata is investigated. A conversion procedure that turns a deterministic set automaton accepting a regular language into a deterministic finite automaton is developed which leads to a double exponential upper bound. This bound is proved to be tight in the order of magnitude by presenting also a double exponential lower bound. In contrast to these recursive bounds we obtain non-recursive trade-offs when nondeterministic set automata are considered.

The quotient of a formal language $K$ by another language $L$ is the set of all strings obtained by taking a string from $K$ that ends with a suffix of a string from $L$, and removing that suffix. The quotient of a regular language by any language is always regular, whereas the context-free languages and many of their subfamilies, such as the linear and the deterministic languages, are not closed under the quotient operation. This paper establishes the closure of the family of languages recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the quotient operation. A construction of automata representing the result of the operation is given, and its state complexity with respect to nondeterministic IDPDA is shown to be exactly $m^{2}n$, where $m$ and $n$ are the numbers of states in the automata recognizing $K$ and $L$, respectively.

Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families ${ℒ}$ that are semilinear full trios, the smallest full AFL containing ${ℒ}$ that is also closed under intersection with languages in $\mathrm{\text{NCM}}$ (where $\mathrm{\text{NCM}}$ is the family of languages accepted by $\mathrm{\text{NFA}}$s augmented with reversal-bounded counters), is also semilinear. If these closure properties are effective, this also immediately implies decidability of membership, emptiness, and infiniteness for these general families. From the general techniques, new grammar systems are given that are extensions of well-known families of semilinear full trios, whereby it is implied that these extensions must only describe semilinear languages. This also implies positive decidability properties for the new systems. Some characterizations of the new families are also given.

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.

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.

Top-down syntax analysis can be based on $\mathrm{\text{LL}}(k)$ grammars. The canonical acceptors for $\mathrm{\text{LL}}(k)$ languages are deterministic stateless pushdown automata with input lookahead of size $k$. We investigate the computational capacity of reversible computations of such automata. A pushdown automaton with lookahead $k$ is said to be reversible if its predecessor configurations can uniquely be computed by a pushdown automaton with backward input lookahead (lookback) of size $k$. It is shown that we cannot trade a lookahead for states or vice versa. The impact of having states or a lookahead depends on the language. While reversible pushdown automata with states accept all regular languages, we are going to prove that there are regular languages that cannot be accepted reversibly without states, even in case of an arbitrarily large lookahead. This completes the comparison of reversible with ordinary pushdown automata in our setting. Moreover, it turns out that there are problems which can be solved by reversible deterministic stateless pushdown automata with lookahead of size $k+1$, but not by any reversible deterministic stateless pushdown automaton with lookahead of size $k$. So, an infinite and tight hierarchy of language families dependent on the size of the lookahead is shown. Finally, we prove that the language families accepted by reversible deterministic stateless pushdown automata with lookahead of size $k$ are not closed under standard operations. For example, we show that the families are anti-AFLs which are not closed under intersection.

We introduce the class ${{𝒞𝒪𝓂}}_S^{+}$ of commutative regular languages that is a positive variety closed under binary shuffle and iterated shuffle (also called shuffle closure). This class arises out of the known positive variety ${{𝒞𝒪𝓂}}^{+}$ by superalphabet closure, an operation on positive varieties we introduce and describe in the present work. We state alternative characterizations for both classes, that the shuffle of any language (resp. any commutative language) with a language from ${{𝒞𝒪𝓂}}^{+}({\mathrm{\Sigma }}^{\ast })$ gives a regular language (resp. a language from ${{𝒞𝒪𝓂}}^{+}({\mathrm{\Sigma }}^{\ast })$) and that ${{𝒞𝒪𝓂}}^{+}$ is also closed for iterated shuffle. Then we introduce the wider class ${ℛ}{𝒞𝒪𝓂}$ that is also closed under iterated shuffle, but fails to be closed for binary shuffle and is not a positive variety. Furthermore, we give an automata-theoretical characterization for the regularity of the iterated shuffle of a regular commutative language. We use this result to show that, for a fixed alphabet, it is decidable in polynomial time whether the iterated shuffle of a commutative regular language given by a deterministic automaton is regular. Lastly, we state some normal form results for the aperiodic, or star-free, commutative languages and the commutative group languages.