Catálogo de publicaciones - libros

We study the decision properties of XML languages. It was known that given a context-free language included in the Dyck language with sufficiently many pairs of parentheses, it is undecidable whether or not it is an XML language. We improve on this result by showing that the problem remains undecidable when the language is written on a unique pair of parentheses. We also prove that if the given language is deterministic, then the problem is decidable; while establishing whether its surfaces are regular turns out to be undecidable whenever the deterministic language is contained in the Dyck language with two pairs of parentheses. Our results are based on a “pumping property” of what Boasson and Berstel call the surface of a context-free language.

We introduce the synchronization of a pushdown automaton by a sequential transducer associating an integer to each input word. The visibly pushdown automata are the automata synchronized by an one state transducer whose output labels are –1,0,1. For each transducer, we can decide whether a pushdown automaton is synchronized. The pushdown automata synchronized by a given transducer accept languages which form an effective boolean algebra containing the regular languages and included in the deterministic real-time context-free languages.

Pushdown automata using a limited and unlimited amount of nondeterminism are investigated. Moreover, nondeterministic steps are allowed only within certain contexts, i.e., in configurations that meet particular conditions. The relationships of the accepted language families with closures of the deterministic context-free languages () under regular operations are studied. For example, automata with unbounded nondeterminism that have to empty their pushdown store up to the initial symbol in order to make a guess are characterized by the regular closure of . Automata that additionally have to reenter the initial state are (almost) characterized by the Kleene star closure of the union closure of the prefix-free deterministic context-free languages. Pushdown automata with bounded nondeterminism are characterized by the union closure of in any of the considered contexts. Proper inclusions between all language classes discussed are shown. Finally, closure properties of these families under AFL operations are investigated.

We investigate factorizations of regular languages in terms of prime languages. A language is said to be strongly prime decomposable if any way of factorizing the language yields a prime decomposition in a finite number of steps. We give a characterization of the strongly prime decomposable regular languages and using the characterization we show that every regular language over a unary alphabet has a prime decomposition. We show that there exist co-context-free languages that do not have prime decompositions.

By weakly ambiguous (finite) transducers we mean those transducers that, although being ambiguous, may be viewed to be at arm’s length from unambiguity. We define input-unambiguous (IU) and input-deterministic (ID) transducers, and transducers with finite codomain (FC). IU transductions are characterized by nondeterministic bimachines and ID transductions can be represented as a composition of sequential functions and finite substitutions. FC transductions are recognizable and can be expressed as finite unions of subsequential functions. We place these families along with uniformly ambiguous (UA) and finitely ambiguous (FA) transductions in a hierarchy of ambiguity. Finally, we show that restricted nondeterministic bimachines characterize FA transductions. Perhaps the most important aspect of this work consists in defining nondeterministic bimachines and describing their power by linking them with weakly ambiguous finite transducers (IU and FA).

We study properties of string operations motivated by the gene assembly process of ciliates. We examine the effect of these operations applied to finite multisets of words which make it possible to study not only sequential, but also different types of parallel derivation strategies. We compare the classes of finite languages which can be obtained by the different strategies, and show that although the string operations we consider are reversible, their parallel application can produce effects resembling the irreversibility of the biological process of gene assembly in ciliates.

We consider the use of DNA trajectories to characterize DNA bond shapes. This is an extension of recent work on the bond-free properties of a language. Using an new definition of bond-freeness, we show that we can increase the types of DNA bond shapes which are expressible. This is motivated by the types of bond shapes frequently found in DNA computing.

We examine the algebraic properties of sets of trajectories. In particular, we consider rotation of trajectories and weakening of the bonding conditions expressed by a set of DNA trajectories. We also consider decidability results for bond-freeness with respect to our definition.

In this paper we study a generalization of the classical notions of solid codes and comma-free codes: involution solid codes (-solid) and involution join codes (-join). These notions are motivated by DNA strand design where Watson-Crick complementarity can be formalized as an antimorphic involution. We investigate closure properties of these codes, as well as necessary conditions for -solid codes to be maximal. We show how the concept of -join can be utilized such that codes that are not themselves -comma free can be split into a union of subcodes that are -comma free.

Boolean grammars [] are a promising extension of context-free grammars that supports conjunction and negation. In this paper we give a novel semantics for boolean grammars which applies to such grammars, independently of their syntax. The key idea of our proposal comes from the area of , and in particular from the so-called which is widely accepted in this area to be the “correct” approach to negation. We show that for every boolean grammar there exists a distinguished (three-valued) language which is a of the grammar and at the same time the least fixed point of an operator associated with the grammar. Every boolean grammar can be transformed into an equivalent (under the new semantics) grammar in normal form. Based on this normal form, we propose an algorithm for parsing that applies to any such normalized boolean grammar. In summary, the main contribution of this paper is to provide a semantics which applies to boolean grammars while at the same time retaining the complexity of parsing associated with this type of grammars.

Tree series transformations computed by polynomial top-down and bottom-up tree series transducers are considered. The hierarchy of tree series transformations obtained in [Fülöp, Gazdag, Vogler: . Theoret. Comput. Sci. 314(3), p. 387–429, 2004] for commutative izz-semirings (izz abbreviates idempotent, zero-sum and zero-divisor free) is generalized to arbitrary positive (, zero-sum and zero-divisor free) commutative semirings. The latter class of semirings includes prominent examples such as the natural numbers semiring and the least common multiple semiring, which are not members of the former class.