Catálogo de publicaciones - libros

Given a class $\mathcal{C}$ of languages, the Inclusion Problem for $\mathcal{C}$ consists of deciding whether for $L_{1},L_{2}\in\mathcal{C}$ we have L _1 ⊆  L _2. In this work we prove that the Inclusion Problem is decidable for the class of unambiguous rational trace languages that are subsets of the monoid ((( a $_{\rm 1}^{\rm \star}$ b $_{\rm 1}^{\rm \star}$ )× c $_{\rm 1}^{\rm \star}$ ) (( a $_{\rm 2}^{\rm \star}$ b $_{\rm 2}^{\rm \star}$ )× c $_{\rm 2}^{\rm \star}$ ))× c $_{\rm 3}^{\rm \star}$ .

The generalized LR parsing algorithm for context-free grammars, invented by Tomita in 1986, is extended for the case of Boolean grammars, which are a recently introduced generalization of 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 makes the algorithm considerably different from its prototype, though it can still be made to work in time O ( n ^3).

We present two new results on 2-collapsing words. First, we show that the language of all 2-collapsing words over 2 letters is not context-free. Second, we prove that the length of a 2-collapsing word over an arbitrary finite alphabet Σ is at least 2|Σ|^2 thus improving the previously known lower bound |Σ|^2 + 1.

We call a set of DAGs (directed acyclic graphs) semi-rational if it is accepted by a Petri net. It is shown that the class of semi-rational sets of DAGs coincides with the synchronization closure of Courcelles class of recognizable sets of unranked, unordered trees (or forests).

It is well-known that the frequency of letters in primitive morphic sequences exists. We show that the frequency of letters exists in pure binary morphic sequences generated by non-primitive morphisms. Therefore, the letter frequency exists in every pure binary morphic sequence. We also show that this is somewhat optimal, in the sense that the result does not hold in the class of general binary morphic sequences. Finally, we give an explicit formula for the frequency of letters.