## Automata Implementation: 4th International Workshop on Implementing Automata, WIA'99 Potsdam, Germany, July 17-19, 2001 Revised PapersThis volume contains the revised versions of papers presented at the fourth international Workshop on Implementing Automata (WIA), held 17-19 July, 1999, at Potsdam University, Germany. As for its predecessors, the theme of WIA99 was the implementation of au- mata and grammars of all types and their application in other ?elds. The papers contributed to this volume address, among others, algorithmic issues regarding automata, image and dictionarystorage byautomata, and natural language p- cessing. In addition to the papers presented in these proceedings, the workshop - cluded a paper on quantum computing byC. Calude, E. Calude, and K. Svozil (published elsewhere), an invited lecture byW. Thomas on Algorithmic P- blems in the Theory of ?-Automata, a tutorial byM. Silberztein on the INTEX linguistic development environment, and several demonstrations of systems. The local arrangements for WIA99 were conducted byHelmut J ̈urgensen, Suna Aydin, Oliver Boldt, Carsten Haustein, Beatrice Mix, and Lynda R- bins. The meeting was held in the Communs building, now the main university building, of the New Palace in the park of Sanssouci, Potsdam. The program committee for WIA99 was: A. Bruggemann-Klein ̈ Technische Universit ̈at Munc ̈ hen J.-M. Champarnaud Universit ́e de Rouen F. Gun ̈ thner Universit ̈at Munc ̈ hen H. Jurgensen ̈ Universit ̈at Potsdam and Universityof Western Ontario D. Maurel Universit ́e de Tours D. Raymond Gateway Group Inc. K. Salomaa Universityof Western Ontario W. Thomas Rheinisch-Westf ̈alische Technische Hochschule Aachen B. Watson Ribbit Software Systems Inc. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

FA Minimisation Heuristics for a Class of Finite Languages | 1 |

A Symbolic Environment for Automata Theory | 13 |

Analysis of Reactive Systems with n Timers | 27 |

Animation of the Generation and Computation of Finite Automata for Learning Software | 39 |

Metric Lexical Analysis | 48 |

State Complexity of Basic Operations on Finite Languages | 60 |

Treatment of Unknown Words | 71 |

Computing Entropy Maps of FiniteAutomatonEncoded Binary Images | 81 |

Finite Automata Encoding Geometric Figures | 101 |

Compressed Storage of Sparse FiniteState Transducers | 109 |

An Extendible Regular Expression Compiler for FiniteState Approaches in Natural Language Processing | 122 |

Multiset Processing by Means of Systems of Finite State Transducers | 140 |

A Structural Method for Output Compaction of Sequential Automata Implemented as Circuits | 158 |

An Algorithm to Verify Local Threshold Testability of Deterministic Finite Automata | 164 |

A Taxonomy of Algorithms for Constructing Minimal Acyclic Deterministic Finite Automata | 174 |

183 | |

### Other editions - View all

Automata Implementation: 4th International Workshop on Implementing Automata ... Oliver Boldt,Helmut Jürgensen No preview available - 2001 |

Automata Implementation: 4th International Workshop on Implementing Automata ... Oliver Boldt,Helmut Jürgensen No preview available - 2001 |

Automata Implementation: 4th International Workshop on Implementing Automata ... Oliver Boldt,Helmut Jürgensen No preview available - 2001 |

### Common terms and phrases

algorithm alphabet animations annotation applied Berlin Heidelberg 2001 biclique covering bipartite graph Boldt and H boolean closure compacted compiler complexity components compression Computational Linguistics Computer Science consider constraint construction corresponding defined deﬁnition denote deterministic distance edges encodable as finite entropy entropy map equivalent event example ﬁnal ﬁnite finite automata finite languages ﬁrst format FSA5 FSTs function given Hausdorff dimension implementation input integer Jürgensen Eds Lemma lexical analyzer lexicon linear locally threshold testable matrix MDFA minimal DFA morphological multiset Natural Language Processing node obtained package parsing possible problem Proof PT system quadtree quasi-distance rational reachable reduction operations regular expression regular expression operators regular language representation rule Salomaa SCC-node semigroup sequence string strongly connected components symbol terminal symbols Theorem Thompson dag Thompson digraph Thompson machine timer transducers transformation transition λ λ λ