|Title||Block-Deterministic Regular Languages|
|Authors||Dora Giammarresi, Dipartimento di Matematica.
Universita' di Roma Tor Vergata
Rosa Montalbano, Dipartimento di Matematica. Universita' di Palermo.
Derick Wood, Department of Computer Science. Hong Kong University of Science and Technology
|Main Fields||2. automata|
|Other Main Fields|
|Abstract + Keywords||We introduce the notion of blocked, block-marked and block-deterministic regular expressions. We characterize block-deterministic regular expressions with deterministic Glushkov block automata. The results can be viewed as a generalization of the characterization of one-unambiguous regular expressions with deterministic Glushkov automata. In addition, when a language L has a block-deterministic expression E, we can construct a deterministic finite-state automaton for L that has size linear in the size of E.|