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.