Catálogo de publicaciones - libros

We propose to capture models where there is a natural linear sequencing of positions and a hierarchically nested matching of positions. Such dual structure exists for executions of structured programs where there is a natural well-nested correspondence among entries to and exits from program components such as functions and procedures, and for XML documents where each open-tag is matched with a closing tag in a well-nested manner.

We define and study finite-state automata as acceptors of nested words. A nested-word automaton is similar to a classical finite-state word automaton, and reads the input from left to right according to the linear sequence. However, at a position with two predecessors, one due to linear sequencing and one due to a hierarchical nesting edge, the next state depends on states of the run at both these predecessors. The resulting class of languages of nested words has all the appealing theoretical properties that the class of classical regular word languages enjoys: deterministic nested word automata are as expressive as their nondeterministic counterparts; the class is closed under operations such as union, intersection, complementation, concatenation, and Kleene-*; decision problems such as membership, emptiness, language inclusion, and language equivalence are all decidable; definability in monadic second order logic of nested words corresponds exactly to finite-state recognizability; and finiteness of the congruence induced by a language of nested words is a necessary and sufficient condition for regularity.

Abstract state machines (originally called evolving algebras) constitute a modern computation model [8]. ASMs describe algorithms without compromising the abstraction level. ASMs and ASM based tools have been used in academia and industry to give precise semantics for computing artifacts and to specify software and hardware [1, 2, 6]. In connection to the conference on Developments in Language Theory, we consider how and whether ASMs could be useful in language theory.

After a brief introduction to membrane computing, pointing out the more important intersections with formal language theory, we survey a series of recent results related to spiking neural P systems used as devices for handling languages. Several open problems are formulated.

The functioning of a living cell consists of a (huge) number of individual biochemical reactions. These reactions are regulated, where the two main regulation mechanisms are: facilitation/acceleration and inhibition/retardation. The interaction between individual biochemical reactions takes place through their influence on each other, and this influence is through facilitation or inhibition (or both).

We show that some language theoretic and logical characterizations of recognizable word languages whose syntactic monoid is in the variety also hold over traces. To this aim we give algebraic characterizations for the language operations of generating the polynomial closure and generating the unambiguous polynomial closure over traces.

We also show that there exist natural fragments of local temporal logic that describe this class of languages corresponding to . All characterizations are known to hold for words.

We introduce weighted automata over infinite words with Muller acceptance condition and we show that their behaviors coincide with the semantics of weighted restricted MSO-sentences. Furthermore, we establish an equivalence property of weighted Muller and weighted Büchi automata over certain semirings.

We adapt the notion of delayed simulation to alternating parity automata and parity games. On the positive side, we show that (i) the corresponding simulation relation can be computed in polynomial time and (ii) delayed simulation implies language inclusion. On the negative side, we point out that quotienting with respect to delayed simulation does not preserve the language recognized, which means that delayed simulation cannot be used for state-space reduction via merging of simulation equivalent states. As a remedy, we introduce finer, so-called biased notions of delayed simulation where we show quotienting does preserve the language recognized. We propose a heuristic for reducing the size of alternating parity automata and parity games and, as an evidence for its usefulness, demonstrate that it is successful when applied to the Jurdziński family of parity games.

A partial function :Σ→Ω is called a function if () ∈Ω is the output produced in the generation of a word ∈Σ from a nonterminal of a simple context free grammar with output alphabet Ω. In this paper we present an efficient algorithm for testing equivalence of simple functions. Such functions correspond also to one-state deterministic pushdown transducers. Our algorithm works in time polynomial with respect to ||+ (), where || is the size of the textual description of , and () is the maximum of the shortest lengths of words generated by nonterminals of .

is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by . Here we introduce and study a new type of restarting automaton, the so-called sRL, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to rewrite (that is, delete) steps per cycle. Here we study the of these automata. The membership problem for a language that is accepted by a -sRL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, -sRL-automata with an unbounded number of gaps accept NP-complete languages.

This paper addresses the longstanding problem of the recognition limitations of classical LALR(1) parser generators by proposing the usage of noncanonical parsers. To this end, we present a definition of noncanonical LALR(1) parsers, NLALR(1). The class of grammars accepted by NLALR(1) parsers is a proper superclass of the NSLR(1) and LALR(1) grammar classes. Among the recognized languages are some nondeterministic languages. The proposed parsers retain many of the qualities of canonical LALR(1) parsers: they are deterministic, easy to construct, and run in linear time. We argue that they could provide the basis for a range of powerful noncanonical parsers.