Catálogo de publicaciones - libros

In this paper, we present a few results which are of interest for the potential application of contextual grammars to natural languages. We introduce two new classes of internal contextual grammars, called and contextual grammars. We analyze the new variants with respect to the basic properties of the languages. With this aim, we show that (i) the three basic in natural languages can be realized upon using these variants, (ii) the for these family of languages is decidable in polynomial time algorithm, (iii) the family of languages generated by end-marked maximal depth-first grammars contains non-semilinear languages. We also solve the following open problem addressed in [3] and [1]: whether the families of languages generated by and contextual grammars are or not?

The class of semi-rational languages can be characterized by labeled Petri nets with -transitions, by rather simple leaf substituting tree grammars with additional non-local merge rules, or as a synchronization closure of Courcelles class of recognizable sets of unranked, unordered trees. However, no direct recognition by some magma is known. For a better understanding, we present here some examples of languages within and without the class of semi-rational languages.

We investigate the following lower bound methods for regular languages: The fooling set technique, the extended fooling set technique, and the biclique edge cover technique. It is shown that the maximal attainable lower bound for each of the above mentioned techniques can be algorithmically deduced from a canonical finite graph, the so called of a regular language. This graph is very helpful when comparing the techniques with each other and with nondeterministic state complexity. In most cases it is shown that for any two techniques the gap between the best bounds can be arbitrarily large. Moreover, we show that deciding whether a certain lower bound w.r.t. one of the investigated techniques can be achieved is in most cases computationally hard, i.e., PSPACE-complete and hence is as hard as minimizing nondeterministic finite automata.

In this paper we consider several reachability problems such as vector reachability, membership in matrix semigroups and reachability problems in piecewise linear maps. Since all of these questions are undecidable in general, we work on lowering the bounds for undecidability. In particular, we show an elementary proof of undecidability of the reachability problem for a set of 7 two-dimensional affine transformations. Then, using a modified version of a standard technique, we also prove the vector reachability problem is undecidable for two (rational) matrices in dimension 16. The above result can be used to show that the system of piecewise linear functions of dimension 17 with only two intervals has an undecidable set-to-point reachability problem. We also show that the “zero in the upper right corner” problem is undecidable for two integral matrices of dimension 18 lowering the bound from 23.

We consider Billiard Words on alphabets with = 3 letters: such words are associated to some 3-dimensional positive vector . The language of these words is already known in the usual case, i.e., when the are linearly independent over , and so for the ’s. Here we study the language of these words when there exist some linear relations. We give the complexity of Billiard Words in any case, which has asymptotically a ”polynomial-like” form, with degree less or equal to 2. These results are obtained by geometrical methods.

68R15.

The complexity (or ) functions of some languages are studied over arbitrary nontrivial alphabets. The attention is focused on the languages determined by a finite set of forbidden factors, called an . Let be a nonnegative integer. Examples of languages of complexity Θ() with finite (and even symmetric finite) antidictionaries are given. For any integer such that 1≤ ≤, a sequence of languages with finite antidictionaries and Θ() complexities, converging to the language of Θ() complexity, is exhibited. Some languages of intermediate complexity are shown to be the limits of sequences of languages with finite antidictionaries and polynomial complexities.

We introduce the polynomial-time tree reducibility (ptt-reducibility). Our main result establishes a one-one correspondence between this reducibility and inclusions between complexity classes. More precisely, for languages and it holds that ptt-reduces to if and only if the leaf-language class of is robustly contained in the unbalanced leaf-language class of . Formerly, such correspondence was only known for leaf-language classes [Bovet, Crescenzi, Silvestri, Vereshchagin].

We show that restricted to regular languages, the levels 0, 1/2, 1, and 3/2 of the dot-depth hierarchy (DDH) are closed under ptt-reducibility. This gives evidence that the correspondence between the dot-depth hierarchy and the polynomial-time hierarchy is closer than formerly known.

Our results also have applications in complexity theory: We obtain the first gap theorem of leaf-language definability above the Boolean closure of NP. Previously, such gap theorems were only known for P,NP, and Σ [Borchert, Kuske, Stephan, and Schmitz].

Systems of language equations of the form =(, ..., ) () are studied, in which every may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is -complete, while the latter is in and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is -complete, and in the case of linear concatenation, where it is -complete. The position of the languages defined by these equations in the hierarchy of language families is established.

We present two infinite series of synchronizing automata with a letter of deficiency 2 whose shortest reset words are longer than those for synchronizing automata obtained by a straightforward modification of Černý’s construction.

Rabin [21] initiated the study of probabilistic finite automata (PFA). Rabin’s work showed a crucial role of the gap in the error bound (for accepting and non-accepting computations) in the power of the model. Further work resulted in the identification of qualitatively different error models (one-sided error, bounded and unbounded errors, no error etc.) Karpinski and Verbeek [16] and Nisan [20] studied a model of probabilistic automaton in which the tape containing random bits can be read by a two-way head. They presented results comparing models with one-way vs. two-way access to randomness. Dwork and Stockmeyer [5] and Condon et al. [4] studied a model of 2-PFA with nondeterministic states (2-NPFA). In this paper, we present some results about the above mentioned variations of probabilistic finite automata, as well as a model of 2-PFA augmented with a pebble studied in [22]. Our observations indicate that these models exhibit subtle variations in their computational power. We also mention many open problems about these models. Complete characterizations of their power will likely provide deeper insights about the role of randomness is space-bounded computations.