Catálogo de publicaciones - libros

We introduce bag context, a device for regulated rewriting in tree grammars. Rather than being part of the developing tree, bag context (bc) evolves on its own during a derivation. We show that the class of bc tree languages is the closure of the class of random context tree languages under linear top-down tree transductions. Further, an interchange theorem for subtrees of dense trees in bc tree languages is established. This result implies that the class of bc tree languages is incomparable with the class of branching synchronization tree languages.

Duplication is an operation generating a language from a single word by iterated application of rewriting rules → on factors. We extend this operation to entire languages and investigate, whether the classes of the Chomsky hierarchy are closed under duplication. Here we treat mainly bounded duplication, where the factors duplicated cannot exceed a given length.

While over two letters the regular languages are closed under bounded duplication, over three or more letters they are not, if the length bound is 4 or greater. For 2 they are closed under duplication, the case of 3 remains open. Finally, the class of context-free languages is closed under duplication over alphabets of any size.

The class of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. GCSL and its deterministic counterpart called Church-Rosser Languages (CRL) complement the Chomsky hierarchy in a natural way [9]. In this paper, the extension of GCSL obtained by closures of this class under the boolean operations are investigated. We show that there exists an infinite intersection hierarchy, answering an open problem from [1]. Further, we compare the expressive power of the boolean closures of GCSL, CRL, CFL and LOGCFL.

Given a set of words, the set L of all words obtained by the shuffle of (copies of) words of is naturally provided with a partial order: for , in L, if and only if is the shuffle of and another word of L. In [3], the authors have stated the problem of the characterization of the finite sets such that is a well quasi-order on L. In this paper we give the answer in the case when consists of a single word .

We introduce -synchronous relations for a rational number . We show that if a rational relation is both - and ′-synchronous for two different numbers and ′, then it is recognizable. We give a synchronization algorithm for -synchronous transducers. We also prove the closure under boolean operations and composition of -synchronous relations.

Let Σ be an alphabet of size , let :Σ→Σ be a non-erasing morphism, let be an infinite fixed point of , and let () be the critical exponent of . We prove that if () is finite, then for a uniform it is rational, and for a non-uniform it lies in the field extension , where ,..., are the eigenvalues of the incidence matrix of . In particular, () is algebraic of degree at most . Under certain conditions, our proof implies an algorithm for computing ().

68R15

In this paper we present a method for solving the -complete SAT problem using the type of P systems that is defined in [9]. The SAT problem is solved in () time, where is the number of boolean variables and is the number of clauses for a instance written in conjunctive normal form. Thus we can say that the solution for each given instance is obtained in linear time. We succeeded in solving SAT by a uniform construction of a deterministic P system which uses rules involving objects in regions, proteins on membranes, and membrane division. We also investigate the computational power of the systems with proteins on membranes and show that the universality can be reached even in the case of systems that do not even use the membrane division and have only one membrane.

The paradigm of is based on the idea that a computing device can be obtained by combining a basic system and an observer that transforms the evolution of the basic system into a readable output. In this framework we investigate what can be computed by changing the observer but not the basic observed system. We consider grammars as basic systems combined with finite state automata as observers, watching either the sequence of sentential forms or the productions used by the grammar. It is possible to obtain computational completeness only varying the observer, without modifying the basic system, which is a fixed context-free grammar.

A structural characterization of reflexive splicing languages has been recently given in [1] and [5] showing surprising connections between long standing notions in formal language theory, the syntactic monoid and Schützenberger constant and the splicing operation.

In this paper, we provide a procedure to decide whether a regular language is a reflexive splicing language, based on the above mentioned characterization that is given in terms of a finite set of constants for the language. The procedure relies on a basic result showing how to determine, given a regular language , a finite set of representatives for constant classes of the syntactic monoid of . This finite set provides the splice sites of splicing rules generating language . Indeed, we recall that in [1] it is shown that a regular splicing language is reflexive iff splice sites of the rules are constants for the language.

In this paper, we introduce contextual hypergraph grammars, which generalize the total contextual string grammars. We study the position of the class of languages generated by contextual hypergraph grammars in comparison with graph languages generated by hyperedge replacement grammars and double-pushout hypergraph grammars. Moreover, several examples show the potential of the new class of grammars.