Narrow Results

In this paper finite state recognizers are considered as unary tree recognizers with unary operational symbols. We introduce translation recognizers of a tree recognizer, which are finite state recognizers whose operations are the elementary translations of the underlying algebra of the considered tree recognizer. In terms of translation recognizers we give general conditions under which a class of recognizable tree languages with a given property can be determined by a class of monoids determining the class of string languages having the same property.

We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. KLÍMA, L. POLÁK: On biautomata. RAIRO — Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages.

This paper deals with insertability and mainly extractablity of codes. A code C is called insertable (or extractable) if the free submonoid C^* generated by C satisfies if z, $xy\in C^{*}$ implies $x\mathrm{zy}\in C^{*}$ (or z, $x\mathrm{zy}\in C^{*}$ implies $xy\in C^{*}$). We show that a finite insertable code is a full uniform code. On the other hand there are many finite extractable codes which are not full uniform codes. We cannot still characterize the structures of infinite extractable codes. Here we give some results on the class of infix extractable codes. First, we consider a necessary and sufficient condition whether a given infix code C is extractable or not by using the syntactic graph of the code. Secondly, we investigate the extractability for the families of other related bifix codes. We newly define the bifix codes, called e(m)-codes and $\overline{e}$-codes, and refer to the extractability of them.

The author shows that the class of groups which are syntactic monoids of deterministic context-free languages is closed under restricted standard wreath products with virtually free top groups. This provides an answer to a question of T. Herbst.

A new type of syntactic monoid and semigroup of tree languages is introduced. For each n ≥ 1, we define for any tree language T its n-ary syntactic monoid Mⁿ(T) and its n-ary syntactic semigroup Sⁿ(T) as quotients of the monoid or semigroup, respectively, formed by certain new generalized contexts. For n = 1 these contexts are just the ordinary contexts (or 'special trees') and M¹(T) is the syntactic monoid introduced by W. Thomas (1982,1984). Several properties of these monoids and semigroups are proved. For example, it is shown that Mⁿ(T) and Sⁿ(T) are isomorphic to certain monoids and semigroups associated with the minimal tree recognizer of T. Using these syntactic monoids or semigroups, we can associate with any variety of finite monoids or semigroups, respectively, a variety of tree languages. Although there are varieties of tree languages that cannot be obtained this way, we prove that the definite tree languages can be characterized by the syntactic semigroups S²(T), which is not possible using the classical syntactic monoids or semigroups.