Narrow Results

Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic. In particular, it is shown that the class of sets representable using k variables (for every k ≥ 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic.

The generalized LR parsing algorithm for context-free grammars is extended for the case of Boolean grammars, which are a generalization of the context-free grammars with logical connectives added to the formalism of rules. In addition to the standard LR operations, Shift and Reduce, the new algorithm uses a third operation called Invalidate, which reverses a previously made reduction. This operation makes the mathematical justification of the algorithm significantly different from its prototype. On the other hand, the changes in the implementation are not very substantial, and the algorithm still works in time O(n⁴).

It was recently found that concatenation of formal languages has a logical dual (A. Okhotin, The dual of concatenation, Theoret. Comput. Sci., 345 (2005), 425–447). In this paper, the closure or nonclosure of common language families under dual concatenation with finite, co-finite and regular languages is determined. In addition, language equations with union, linear concatenation and dual concatenation with co-finite constants are shown to be almost equal in power to linear conjunctive grammars.

Conjunctive grammars, introduced by Okhotin, extend context-free grammars by an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Okhotin posed nine open problems concerning those grammars. One of them was a question, whether a conjunctive grammars over a unary alphabet generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language {a⁴ⁿ : n ∈ ℕ}. We also generalize this result: for every set of natural numbers L we show that {aⁿ : n ∈ L} is a conjunctive unary language, whenever the set of representations in base-k system of elements of L is regular, for arbitrary k.

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.

Systems of equations of the form X = Y + Z and X = C, in which the unknowns are sets of natural numbers, "+" denotes elementwise sum of sets S + T = {m + n | m ∈ S, n ∈ T}, and C is an ultimately periodic constant, have recently been proved to be computationally universal (Jeż, Okhotin, "Equations over sets of natural numbers with addition only", STACS 2009). This paper establishes some limitations of such systems. A class of sets of numbers that cannot be represented by unique, least or greatest solutions of systems of this form is defined, and a particular set in this class is constructed. The argument is then extended to equations over sets of integers.

We study decompositions of a factorial language to catenations of factorial languages and introduce the notion of a canonical decomposition. Then we prove that for each factorial language, a canonical decomposition exists and is unique.