Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2011 | Book

Derick Wood: Always in Our Hearts Read chapter Read first chapter

Implementation and Application of Automata

16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011. Proceedings

Editors: Béatrice Bouchou-Markhoff, Pascal Caron, Jean-Marc Champarnaud, Denis Maurel

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the thoroughly refereed papers of the 16th International Conference on Implementation and Application of Automata, CIAA 2011, held in Blois, France, in July 2011. The 20 revised full papers together with 4 short papers were carefully selected from 38 submissions. The papers cover various topics such as applications of automata in computer-aided verification; natural language processing; pattern matching, data storage and retrieval; document engineering and bioinformatics as well as foundational work on automata theory.

Table of Contents

Frontmatter

Invited Lectures

Derick Wood: Always in Our Hearts
Abstract
Professor Derick Wood passed away on October 4, 2010. He was only seventy year old. His death was a great loss to his family, friends, colleagues and students, especially to his beloved wife Mary. He left us many interesting research results, more than three hundred publications [1], including three monograph and textbooks [3,4,5], and a lot of vivid memories of an energetic, thoughtful, humorous, careful, and decisive Derick Wood.
Sheng Yu
Streamable Fragments of Forward XPath
Abstract
We present a query answering algorithm for a fragment of Forward XPath on Xml streams that we obtain by compilation to deterministic nested word automata. Our algorithm is earliest and in polynomial time. This proves the finite streamability of the fragment of Forward XPath with child steps, outermost-descendant steps, label tests, negation, and conjunction (aka filters), under the reasonable assumption that the number of conjunctions is bounded. We also prove that finite streamability fails without this assumption except if P=NP.
Olivier Gauwin, Joachim Niehren
Gaining Power by Input Operations: Finite Automata and Beyond
Abstract
We summarize results on extended finite automata, which are basically finite state machines with the additional ability to manipulate the still unread part of the input. Well-known manipulation functions are reversal, left-revolving, right-revolving, and circular interchanging, or even biologically motivated functions as hairpin inversion. We mainly focus on the computational power of these machines and on the closure properties by standard formal language operations of the induced language families. Moreover, we also discuss several generalizations of this concept, the natural generalization to hybrid extended finite automata, which allows several input manipulation functions, and in particular, extended pushdown automata, which lead to an alternative characterization of Khabbaz hierarchy of languages. We do not prove these results but we merely draw attention to the big picture, some of the main ideas involved, and open problems for further research.
Markus Holzer, Martin Kutrib

Technical Contributions

Weak Inclusion for XML Types
Abstract
Considering that the unranked tree languages L(G) and L(G′) are those defined by given non-recursive XML types G and G′, this paper proposes a simple and intuitive method to verify whether L(G) is “approximatively” included in L(G′). Our approximative criterion consists in weakening the father-children relationships. Experimental results are discussed, showing the efficiency of our method in many situations.
Joshua Amavi, Jacques Chabin, Mirian Halfeld Ferrari, Pierre Réty
Categorial Grammars with Iterated Types form a Strict Hierarchy of k-Valued Languages
Abstract
The notion of k-valued categorial grammars where a word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining several properties like the existence of learning algorithms. This principle is relevant only when the classes of k-valued grammars correspond to a real hierarchy of languages. Such a property had been shown earlier for classical categorial grammars.
This paper establishes the relevance of this notion when categorial grammars are enriched with iterated types.
Denis Béchet, Alexandre Dikovsky, Annie Foret
Bouma2 – A High-Performance Input-Aware Multiple String-Match Algorithm
Abstract
We present Bouma2, a new algorithm for exact multiple string-match. It is highly parallelizable, has small footprint, and can be tuned using statistics of the input stream. It uses a special hashing technique to map the pattern-set to 2-symbol sequences, allowing the match procedure to be considerably optimized. This algorithm employs a fast-path/slow-path principle at match-time, which facilitates pipelining in H/W. We also produce experimental comparative results.
Erez Buchnik
Random Generation of Deterministic Acyclic Automata Using Markov Chains
Abstract
In this article we propose an algorithm, based on Markov chain techniques, to generate random automata that are deterministic, accessible and acyclic. The distribution of the output approaches the uniform distribution on n-state such automata. We then show how to adapt this algorithm in order to generate minimal acyclic automata with n states almost uniformly.
Vincent Carnino, Sven De Felice
Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability
Abstract
We use a finite state (FSA) construction approach to address the problem of propositional satisfiability (SAT). We use a very simple translation from formulas in conjunctive normal form (CNF) to regular expressions and use regular expressions to construct an FSA. As a consequence of the FSA construction, we obtain an ALL-SAT solver and model counter. We compare how several variable ordering (state ordering) heuristics affect the running time of the FSA construction. We also present a strategy for clause ordering (automata composition). We compare the running time of state-of-the-art model counters, BDD based sat solvers and we show that this FSA approach obtains state-of-the-art performance on some hard unsatisfiable benchmarks. This work brings up many questions on the possible use of automata to address SAT.
José M. Castaño, Rodrigo Castaño
Nondeterministic Moore Automata and Brzozowski’s Algorithm
Abstract
Moore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. In this paper we propose an algorithm that is a variant of Brzozowski’s algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.
Giusi Castiglione, Antonio Restivo, Marinella Sciortino
Building Phylogeny with Minimal Absent Words
Abstract
An absent word in a sequence is a segment that does not occur in the given sequence. It is a minimal absent word if all its proper factors occur in the given sequence.
In this paper, we review the concept of minimal absent words, which includes the notion of shortest absent words but is much stronger. We present an efficient method for computing the minimal absent words of bounded length for DNA sequence using a Suffix Trie of bounded depth, representing bounded length factors. This method outputs the whole set of minimal absent words and furthermore our technique provides a linear-time algorithm with less memory usage than previous solutions.
We also present an approach to distinguish sequences of different organisms using their minimal absent words. Our solution applies a length-weighted index to discriminate sequences and the results show that we can build phylogenetic tree based on the collected information.
Supaporn Chairungsee, Maxime Crochemore
On the Hardness of Priority Synthesis
Abstract
We study properties of priority synthesis [2], an automatic method to ensure desired safety properties in component-based systems using priorities. Priorities are a powerful concept to orchestrate components [3], e.g., the BIP framework [1] for designing and modeling embedded and autonomous systems is based on this concept.
We formulate priority synthesis for BIP systems using the automata-theoretic framework proposed by Ramadge and Wonham [5]. In this framework, priority synthesis results in searching for a supervisor from the restricted class of supervisors, in which each is solidly expressible using priorities. While priority-based supervisors are easier to use, e.g., they support the construction of distributed protocols, they are harder to compute. In this paper, we focus on the hardness of synthesizing priorities and show that finding a supervisor based on priorities that ensures deadlock freedom of the supervised system is NP-complete.
Chih-Hong Cheng, Barbara Jobstmann, Christian Buckl, Alois Knoll
Smaller Representation of Finite State Automata
Abstract
This paper is a follow-up to Jan Daciuk’s experiments on space-efficient finite state automata representation that can be used directly for traversals in main memory [4]. We investigate several techniques of reducing the memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve a size gain of around 20–30% compared to the original representation given in [4]. This result is comparable to the state-of-the-art dictionary compression techniques like the LZ-trie [10] method, but remains memory and CPU efficient during construction.
Jan Daciuk, Dawid Weiss
Compositional Failure Detection in Structured Transition Systems
Abstract
In model-checking, systems are often given as products. We propose an approach that is built on a preprocessing of specifications in terms of appropriate automata. This allows to incorporate information about the local behaviour and synchronization of the system components into the specification. We develop a framework of (partially) synchronized automaton products and a format of corresponding specification automata that allows for a compositional failure detection of linear regular properties (either for finite or for infinite behaviour). As a result we obtain an algorithm which separates the local and the non-local segments of system runs, resulting in improved complexity bounds in typical specifications.
Ingo Felscher, Wolfgang Thomas
Chrobak Normal Form Revisited, with Applications
Abstract
It is well known that any nondeterministic finite automata over a unary alphabet can be represented in a certain normal form called the Chrobak normal form [1]. We present a very simple conversion procedure working in \(\mathcal{O}(n^3)\) time. Then we extend the algorithm to improve two trade-offs concerning conversions between different representations of unary regular languages. Given an n-state NFA, we are able to find a regular expression of size \(\mathcal{O}(\frac{n^2}{\log^2 n})\) describing the same language (which improves the previously known \(\mathcal{O}(n^2)\) size bound [8]) and a context-free grammar in Chomsky normal form with \(\mathcal{O}(\sqrt{n\log n})\) nonterminals (which improves the previously known \(\mathcal{O}(n^{2/3})\) bound [3]).
Paweł Gawrychowski
A Cellular Automaton Model for Car Traffic with a Form-One-Lane Rule
Abstract
We propose a cellular automaton model that simulates a traffic flow with a junction. We include a ‘form-one-lane’ rule that decides which car moves ahead when two cars on two different lanes are in front of a junction. We present a fundamental diagram of the proposed model and car distribution examples. We also demonstrate that the proposed model is useful for predicting the real-world traffic flow with a junction.
Yo-Sub Han, Sang-Ki Ko
Loops and Overloops for Tree Walking Automata
Abstract
Tree Walking Automata (TWA) have lately received renewed interest thanks to their tight connection to XML. This paper introduces the notion of tree overloops, which is closely related to tree loops, and investigates the use of both for the following common operations on TWA: testing membership, transformation into a Bottom-Up Tree Automaton (BUTA), and testing emptiness. Notably, we argue that transformation into a BUTA is slightly less straightforward than was assumed, show that using overloops yields much smaller BUTA in the deterministic case, and provide a polynomial over-approximation of this construction which detects emptiness with surprising accuracy against randomly generated TWA.
Pierre-Cyrille Héam, Vincent Hugot, Olga Kouchnarenko
Nondeterministic State Complexity of Star-Free Languages
Abstract
We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained in [8] for the operation problem of star-free languages accepted by deterministic finite automata.
Markus Holzer, Martin Kutrib, Katja Meckel
On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs
Abstract
We explore the boundaries between decidability and undecidability of the containment and equivalence problems for restricted classes of nondeterministic generalized sequential machines (NGSMs), nondeterministic finite transducers (NFTs), nondeterministic pushdown transducers (NPDTs), and linear context-free grammars (LCFGs). We believe that our results are the sharpest known to date concerning these devices.
Oscar H. Ibarra
Computing All ℓ-Cover Automata Fast
Abstract
Given a language L and a number ℓ, an ℓ-cover automaton for L is a DFA M such that its language coincides with L on all words of length at most ℓ. It is known that an equivalent minimal ℓ-cover automaton can be constructed in time \(\mathcal{O}(n \log n)\), where n is the number of states of M. This is achieved by a clever and sophisticated variant of Hopcroft’s algorithm, which computes the ℓ-similarity inside the main algorithm. This contribution presents an alternative simple algorithm with running time \(\mathcal{O}(n \log n)\), in which the computation is split into three phases. First, a compact representation of the gap table is created. Second, this representation is enriched with information about the length of a shortest word leading to the states. These two steps are independent of the parameter ℓ. Third, the ℓ-similarity is extracted by simple comparisons against ℓ. In particular, this approach allows the calculation of all the sizes of minimal ℓ-cover automata (for all valid ℓ) in the same time bound.
Artur Jeż, Andreas Maletti
Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines
Abstract
In this paper, we present algorithms for preset and adaptive homing experiments for a given observable reduced nondeterministic finite state machine (NFSM). We show that the tight upper bound on a shortest preset homing sequence for a NFSM with n states and with two or more initial states is of order \(2{^{n}}^{^2}\). The upper bound on a shortest adaptive homing sequence of a NFSM with m initial states, m ( n, states is of order \(\sum\limits_{j=2}^m C_n^j\) and this upper bound is of order 2 n when m tends to n.
Natalia Kushik, Khaled El-Fakih, Nina Yevtushenko
Towards More Expressive 2D Deterministic Automata
Abstract
REC defines an important class of picture languages that is considered a 2D analogous of regular languages. In this paper we recall some of the most expressive operational approaches to define deterministic subclasses of REC. We summarize their main characteristics and properties and try to understand if it is possible to combine their main features to define a larger deterministic subclass. We conclude by proposing a convenient generalization based on automata and study some of its formal properties.
Violetta Lonati, Matteo Pradella
Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata
Abstract
A word is called a reset word for a deterministic finite automaton if it maps all states of this automaton to one state. We consider two classes of automata: cyclic automata and Eulerian automata. For these classes we study the computational complexity of the following problems: does there exist a reset word of given length for a given automaton? what is the minimal length of the reset words for a given automaton?
Pavel Martyugin
Distributed Event Clock Automata
Extended Abstract
Abstract
In distributed real-time systems, we cannot assume that clocks are perfectly synchronized. To model them, we use independent clocks and define their timed semantics. The universal timed language, and the timed language inclusion of icTA are undecidable. Thus, we propose Recursive Distributed Event Clock Automata (DECA). DECA are closed under all boolean operations and their timed language inclusion problem is decidable (more precisely PSPACE-complete), allowing stepwise refinement. We also propose Distributed Event Clock Temporal Logic (DECTL), a real-time logic with independent time evolutions. This logic can be model-checked by translating a DECTL formula into a DECA automaton.
James Ortiz, Axel Legay, Pierre-Yves Schobbens

Short Papers

Fly-Automata, Their Properties and Applications
Abstract
We address the concrete problem of implementing huge bottom-up term automata. Such automata arise from the verification of Monadic Second Order propositions on graphs of bounded tree-width or clique-width. This applies to graphs of bounded tree-width because bounded tree-width implies bounded clique-width. An automaton which has so many transitions that they cannot be stored in a transition table is represented be a fly-automaton in which the transition function is represented by a finite set of meta-rules.
Fly-automata have been implemented inside the Autowrite software and experiments have been run in the domain of graph model checking.
Bruno Courcelle, Irène A. Durand
Tree Template Matching in Ranked Ordered Trees by Pushdown Automata
Abstract
We consider the problem of tree template matching in ranked ordered trees, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix notation, and then use pushdown automata as the computational model. The method is analogous to the construction of string pattern matchers. The given tree template is preprocessed once, by constructing a nondeterministic pushdown automaton, which is then transformed to the equivalent deterministic one. Although we prove that the space required for preprocessing is exponential to the size of the tree template in the general case, the space required for a specific class of tree templates is linear. The time required for the searching phase is linear to the size of the subject tree in both cases.
Tomáš Flouri, Jan Janoušek, Bořivoj Melichar, Costas S. Iliopoulos, Solon P. Pissis
Information Extraction from Semi-structured Resources: A Two-Phase Finite State Transducers Approach
Abstract
The paper presents a new method for extracting information from semi-structured resources, based on finite state transducers. The method has two clearly distinguished phases. The first phase - pre-processing phase - strongly relies upon the analysis of the document structure and it is used for locating records of data in the text. The second phase is based on the finite state transducers created for extracting information. The transducers can be modified so that preferred efficiency is achieved and can be reused for extracting information from other pre-processed documents. We conclude that even untagged text can be treated as a semi-structured one, providing its structure can be successfully pre-processed. As a result, we extracted data from free form encyclopedia text and created a fully structured database with genotype and phenotype characteristics of the organisms.
Vesna Pajić, Gordana Pavlović Lažetić, Miloš Pajić
Experimental Study of the Shortest Reset Word of Random Automata
Abstract
In this paper we describe an approach to finding the shortest reset word of a finite synchronizing automaton by using a SAT solver. We use this approach to perform an experimental study of the length of the shortest reset word of a finite synchronizing automaton. The largest automata we considered had 100 states. The results of the experiments allow us to formulate a hypothesis that the length of the shortest reset word of a random finite automaton with n states and 2 input letters with high probability is sublinear with respect to n and can be estimated as 1.95 n 0.55.
Evgeny Skvortsov, Evgeny Tipikin
Backmatter
Metadata
Title
Implementation and Application of Automata
Editors
Béatrice Bouchou-Markhoff
Pascal Caron
Jean-Marc Champarnaud
Denis Maurel
Copyright Year
2011
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-22256-6
Print ISBN
978-3-642-22255-9
DOI
https://doi.org/10.1007/978-3-642-22256-6

Premium Partner

    Image Credits