Titlebook: Implementation and Application of Automata; 18th International C Stavros Konstantinidis Conference proceedings 2013 Springer-Verlag Berlin

tooth-decay

Two-Pass Greedy Regular Expression Parsingme .(.) for REs of size . and input strings of size . and outputs a compact bit-coded parse tree representation. It improves on previous algorithms by: operating in only 2 passes; using only .(.) words of random-access memory (independent of .); requiring only .. bits of sequentially written and rea

jet-lag

Universal Witnesses for State Complexity of Basic Operations Combined with Reversalr bounds for the symmetric differences and differences of such languages. We prove that the previously discovered bounds for union, intersection, concatenation and star of such languages can all be met by the recently introduced universal witness and its variants.

Graves’-disease

CLAM

A Uniformization Theorem for Nested Word to Word Transductionsation can be uniformized by a functional relation from the same class, implemented by an unambiguous transducer. We give an exponential upper bound on the state complexity of the uniformization, improving a previous doubly exponential upper bound. Our construction generalizes a classical constructio

Vertebra

Occupation

Implementation Concepts in Vaucanson 2of mathematical objects. Initiated ten years ago, several shortcomings were discovered along the years, especially problems related to code complexity and obfuscation as well as performance issues. This paper presents the concepts underlying ., a complete rewrite of the platform that addresses these

Redundant

A Completion Algorithm for Lattice Tree Automatapose Lattice Tree Automata, an extended version of tree automata to represent complex data domains and their related operations in an efficient manner. Moreover, we introduce a new completion-based algorithm for computing the possibly infinite set of reachable states in a finite amount of time. This

adulterant

Approximate Matching between a Context-Free Grammar and a Finite-State Automatonguages. We in particular consider three different gap cost models, linear, affine and concave models, that are crucial for finding a proper alignment between two bio sequences. We design efficient algorithms for computing the edit-distance between a CFG and an FA under these gap cost models. The tim

和平主义者

Brzozowski’s Minimization Algorithm—More Robust than Expectedl deterministic finite automaton by applying reversal and power-set construction twice. Although this is an exponential algorithm because of the power-set construction, it performs well in experimental studies compared to efficient .(.log.) minimization algorithms. Here we show how to slightly enhan

Entropion

Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languagesther the NPDA makes a bounded number of stack reversals (over all accepting inputs) and show that this problem is undecidable even when the NPDA is only 2-ambiguous. We consider the same problem for counter machines (i.e., whether the counter makes a bounded number of reversals) and show that it is