No CrossRef data available.
Article contents
Conversion of regular expressionsinto realtime automata
Published online by Cambridge University Press: 08 November 2006
Abstract
We consider conversions of regular expressions into k-realtimefinite state automata, i.e., automata in which the number ofconsecutive uses of ε-transitions, along any computation path,is bounded by a fixed constant k. For 2-realtime automata,i.e., for automata that cannot change the state, without readingan input symbol, more than two times in a row, we show that theconversion of a regular expression into such an automaton producesonly O(n) states, O(nlogn) ε-transitions, and O(n)alphabet-transitions. We also show how to easily transform these2-realtime machines into 1-realtime automata, still with onlyO(nlogn) edges. These results contrast with the known lowerbound Ω(n(logn)2 / loglogn), holding for 0-realtimeautomata, i.e., for automata with no ε-transitions.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 4 , October 2006 , pp. 611 - 629
- Copyright
- © EDP Sciences, 2006