Titlebook: Implementation and Application of Automata; 10th International C Jacques Farré,Igor Litovsky,Sylvain Schmitz Conference proceedings 2006 Sp

分解

Minimization of Non-deterministic Automata with Large Alphabetss the one suggested by Paige and Tarjan. The algorithm has a complexity of .(. log .) where . is the number of edges and . is the number of states in the automaton. A bottleneck in the application of the algorithm is often the number of labels which may appear on the edges of the automaton. In this

伟大

Simulating Two-Dimensional Recognizability by Pushdown and Queue Automataer to encompass a wider class of languages. We show that any (tiling) recognizable language can be simulated by a 4NFA with an extra queue whose size is bounded by the minimum of the two dimensions of a picture; and that 2NFA (i.e. automata moving only in two directions) with an analogous queue are

石墨

时代

Aggressive

Prime Normal Form and Equivalence of Simple Grammarsl time if a language generated by a simple context-free grammar is a prime. Our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into Prime Normal Form (PNF); a simple grammar is in PNF if all its nonterminals define primes. We also improve

BOLT

An Incremental Algorithm for Constructing Minimal Deterministic Finite Cover Automata less states than the DFA for ., this technique seems to be the best choice for incrementally building the automaton for a large language, especially when the number of states in the DFCA is significantly less than the number of states in the corresponding minimal DFA. We have implemented the propos

CODE

Finite Automata and Unions of Regular Patterns with Bounded Constant Segmentsse, no efficient algorithm that performs the inference of this class of languages is known. We propose a solution to this problem using the existing connexion between the positive variety of languages of dot depth 1/2, . [2] and the class of unbounded union of pattern languages ..

乐章

Inside Vaucansontient, conversion of a regular expression into a weighted automaton, and composition). We explain how complex declarations due to the generic programming are masked from the user and finally we present a proposal for an XML format that allows implicit descriptions for simple types of automata.

arousal

Deterministic Recognition of Trees Accepted by a Linear Pushdown Tree AutomatonDTAs) 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

emission

Shorter Regular Expressions from Finite-State Automatave 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 hor