Catálogo de publicaciones - libros

In this paper, a deterministic recognition algorithm for the class of tree languages accepted by (nondeterministic) linear pushdown tree automata (L-PDTAs) is proposed. L-PDTAs accept an important class of tree languages since the class of their yield languages coincides with the class of yield languages generated by tree adjoining grammars (TAGs). The proposed algorithm is obtained by combining a bottom-up parsing procedure on trees with the CKY (Cocke-Kasami-Younger) algorithm. The running time of the algorithm is (), where is the number of nodes of an input tree.

We consider the use of state elimination to construct shorter regular expressions from finite-state automata. Although state elimination is an intuitive method for computing regular expressions from finite-state automata, the resulting regular expressions are often very long and complicated. We examine the minimization of finite-state automata to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given finite-state automata. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that lead to shorter regular expressions based on vertical chopping and horizontal chopping.

Note that we have omitted almost all proofs in this preliminary version.

We implement a rule-based system for algorithmic composition. This system, that we call Willow, resides in the environment and consists of a sequence of formal devices, familiar from the field of tree grammars and tree transducers. Since these devices are well studied, we can apply known results to derive the descriptive complexity of the system as a whole.

We look at a 1-membrane catalytic P system with evolution rules of the form → or →, where is a catalyst, is a noncatalyst symbol, and is a (possibly null) string representing a multiset of noncatalyst symbols. (Note that we are only interested in the multiplicities of the symbols.) A catalytic system can be regarded as a in the following sense. Given an input alphabet Σ consisting of noncatalyst symbols, the system starts with an initial configuration , where is a fixed string of catalysts and noncatalysts not containing any symbol in , and for some nonnegative integers , ..., , with { ... } ⊆ ∑. At each step, a maximal multiset of rules is nondeterministically selected and applied in parallel to the current configuration to derive the next configuration (note that the next configuration is not unique, in general). The string is accepted if the system eventually halts.

It is known that a 1-membrane catalytic system is universal in the sense that any unary recursively enumerable language can be accepted by a 1-membrane catalytic system (even by purely catalytic systems, i.e., when all rules are of the form → ). A catalytic system is said to be if at each step, there is a maximally parallel multiset of rules applicable. It has been an open problem whether deterministic systems of this kind are universal. We answer this question negatively: We show that the membership problem for deterministic catalytic systems is decidable. In fact, we show that the Parikh map of the language ( ) accepted by any deterministic catalytic system is a simple semilinear set which can be effectively constructed. Since nondeterministic 1-membrane catalytic system acceptors (with 2 catalysts) are universal, our result gives the first example of a variant of P systems for which the nondeterministic version is universal, but the deterministic version is not.

We also show that for a deterministic 1-membrane catalytic system using only rules of type →, the set of reachable configurations from a given initial configuration is an effective semilinear set. The application of rules of type →, however, is sufficient to render the reachability set non-semilinear. Our results generalize to multi-membrane deterministic catalytic systems. We also consider deterministic catalytic systems which allow rules to be prioritized and investigate three classes of such systems, depending on how priority in the application of the rules is interpreted. For these three prioritized systems, we obtain contrasting results: two are universal and one only accepts semilinear sets.

The most general models of restarting automata make use of auxiliary symbols in their rewrite operations. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Weighted finite-state machines with tapes describe -ary rational string relations. The join -ary relation is very important in applications. It is shown how to compute it via a more simple operation, the auto-intersection. Join and auto-intersection generally do not preserve rationality. We define a class of triples 〈, , 〉 such that the auto-intersection of the machine on tapes and can be computed by a delay-based algorithm. We point out how to extend this class and hope that it is sufficient for many practical applications.

This paper addresses the problem of generating deterministic -automata for formulas of linear temporal logic, which can be solved by applying well-known algorithms to construct a nondeterministic Büchi automaton for the given formula on which we then apply a determinization algorithm. We study here in detail Safra’s determinization algorithm, present several heuristics that attempt to decrease the size of the resulting automata and report on experimental results.

Number Decision Diagrams (NDD) are finite automata representing sets of integer vectors and have recently been proposed as an efficient data structure for representing sets definable in Presburger arithmetic. In this context, some work has been done in order to generate formulas or sets of generators from the NDDs. Taking another step in this direction, this paper present algorithms that takes as input an NDD and computes the affine hull over or over of the set represented by the NDD, i.e., the smallest set defined by a conjunction of equations or by a conjunction of equations and congruence relations that includes the set represented by the NDD. Our algorithms run in time and respectively, where is the number of components of the vectors represented by the NDD, and || and Σ are the number of states and the alphabet of the NDD. On a prototype implementation, the computations of affine hulls of NDDs with more than 100000 states are done in seconds.

The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated.

It is known that Linear Temporal Logic (LTL) has the same expressive power as alternating 1-weak automata (A1W automata, also called alternating linear automata or very weak alternating automata). A translation of LTL formulae into a language equivalent A1W automata has been introduced in [1]. The inverse translation has been developed independently in [2] and [3]. In the first part of the paper we show that the latter translation wastes temporal operators and we propose some improvements of this translation. The second part of the paper draws a direct connection between fragments of the Until-Release hierarchy [4] and alternation depth of nonaccepting and accepting states in A1W automata. We also indicate some corollaries and applications of these results.