ABSTRACT. In this paper we consider two classes of posets labeled over an alphabet A. The class SP^.(A) is built from the letters and closed under the operations of series finite, ω and \overline{ω} products, and finite parallel product. In the class ^ωSP(A), ω and \overline{ω} products are replaced by ω and \overline{ω} powers. We prove that SP^⋄(A) and ^ωSP(A) are freely generated in their respective natural varieties of algebras V and V′, and that the equational theory of V′ is decidable.

ABSTRACT. A modifier is a k-ary operator acting on DFAs and producing a DFA. Modifiers are involved in the theory of state complexity. We define and study a class of simple modifiers, called product modifiers, and we link closely the regular operations they encode to boolean operations.

ABSTRACT. A language over an alphabet B = A U ~A of opening (A) and closing (~A) brackets, is balanced if it is a subset of the Dyck language DB over B, and it is well-formed if all words are prefixes of words in DB. 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-TW of non-linear tree transducers with output alphabet B∗ whether or not the output language is balanced.

ABSTRACT. In this paper we provide a decidable characterisation of the context-freeness of a Word-MIX language LA(w1,...,wk), where LA(w1,...,wk) is the set of all words over A that contain the same number of subword occurrences of parameter words w1,...,wk.

ABSTRACT. A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound B(G) of a PEG G such that L(G) has a string w of length at most B(G).

ABSTRACT. Tree substitution grammars are formal models that are used extensively in natural language processing. It is demonstrated that their expressive power is located strictly between the local tree grammars and the regular tree grammars. A decision procedure for the problem of determining whether a tree substitution grammar generates a local tree language is provided. Unfortunately, the class of tree substitution languages is neither closed under union, nor intersection, nor complements. Indeed unions of tree substitution languages even generate an infinite hierarchy. However, all finite and all co-finite tree languages are tree substitution languages.

ABSTRACT. In 1842, Dirichlet observed that any real number α can be obtained as the limit of a sequence (p_n/q_n ) of irreducible rational numbers. Few years later, M. Stern (1858) and A. Brocot (1861) defined a tree-like arrangement of all the (irreducible) rational numbers whose infinite paths are the Dirichlet sequences of the real numbers and are characterized by their continued fraction representations. The Stern-Brocot tree is equivalent to the Christoffel tree obtained by ordering the Christoffel words according to their standard factorization. We remark that the Fibonacci word’s prefixes belong to a minimal path in the Christoffel tree with respect to the second order balancedness parameter defined on Christoffel words. This allows us to switch back to the Stern-Brocot tree, in order to give a characterization of the continued fraction representation for all the rational numbers belonging to minimal paths with respect to the growth of the second order balancedness.

ABSTRACT. Let A ⊂ N be a set of size 4 such that A cannot be obtained by applying the same affine function to all of the elements of {0, 1, 2, 3}. We show that there is an infinite sequence of elements of A that contains no three consecutive blocks of same size and same sum (additive cubes). Moreover, it is possible to replace N by C in the statement.

ABSTRACT. 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 Ω(√n) as the (tight) time complexity threshold for DACAs up to which no advantage compared to constant time is possible.

ABSTRACT. We show that equivalence of deterministic linear tree transducers can be decided in polynomial time when their outputs are interpreted over the free group. Due to the cancellation properties offered by the free group, the required constructions are not only more general, but also simpler than the corresponding constructions for proving equivalence of deterministic linear tree-to-word transducers.

ABSTRACT. Let G be a group and H₁,. . . , H_s be subgroups of G of indices d₁, . . . , d_s respectively. In 1974, M. Herzog and J. Schönheim conjectured that if {H_i,α_i}_{i=1}^{i=s} ∈ G, is a coset partition of G, then d₁,...,d_s cannot be distinct. In this paper, we present a new approach to the Herzog-Schönheim conjecture based on automata and present a translation of the conjecture as a problem on automata.

ABSTRACT. We investigate the class of languages recognized by permutation deterministic finite automata. Using automata constructions and some properties of permutation automata, we show that this class is closed under Boolean operations, reversal, and quotients, and it is not closed under concatenation, power, Kleene closure, positive closure, cut, shuffle, cyclic shift, and permutation. We prove that the state complexity of Boolean operations, Kleene closure, positive closure, and right quotient on permutation languages is the same as in the general case of regular languages. Next, we get tight upper bounds on the state complexity of concatenation, square, reversal and left quotient. All our witnesses are unary or binary, and the binary alphabet is always optimal, except for Boolean operations in the case of gcd(m, n) = 1. In the unary case, the state complexity of all considered operations is the same as for regular languages, except for quotients and cut.

ABSTRACT. We consider general expressions, which are trees whose nodes are labeled with operators, that represent syntactic descriptions of formulas. 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. In our framework, expressions are defined using a combinatorial system, which describes how they are built: one can ensure, for instance, that there are no two consecutive stars in regular expressions. This generalizes a former result where only one equation was allowed, confirming the lack of expressivity of uniform random expressions.

ABSTRACT. We study the problem of finding a given 2×2 matrix as a submatrix of a given Boolean matrix. Three variants are considered: search for a matching submatrix of any area, of minimum area, or of maximum area. The problem relates to 2D pattern matching, and to fields such as data mining, where the search for submatrices plays an important role. Besides these connections, the problem itself is very natural and its investigation helps to demonstrate differences between search tasks in one-dimensional and multidimensional topologies. Our results reveal that the problem variants are of different complexities. First, we show that given an m × n Boolean matrix, the any variant can be solved in O(mn) time for any given 2 × 2 matrix, but requires various strategies for different 2 × 2 matrices. This contrasts with the complexity of the task over matrices with entries from the set {0, 1, 2}, where the problem is Triangle Finding-hard and hence no algorithm with similar running time is known for it. Then, we show that the minimization variant in the case of Boolean matrices can also be solved in O(mn) time. Finally, in contrast, we prove Triangle Finding-hardness for the maximization variant and show that there is a rectangular matrix multiplication-based algorithm solving it in O(mn(min{m,n})^0.5302) time.