| In environments like the Web, where the networks are not always reliable, it is possible that a continuous stream of data gets interrupted. To continue processing when the stream flow is restored, we have to remember the states in which the finite-state automaton was at the moment of the interruption. Our goal is to characterize classes of nonrecursive DTDs (Document Type Definition) for which on-line validation is performed by a deterministic finite-state automaton. The first class we consider contains DTDs that use only one-unambiguous regular expressions. Then, we generalize to a new class of DTDs that contain k-unambiguous regular expressions. The k-unambiguous regular expressions are a generalization of the one-unambiguous regular expressions. We investigate several characterizations of this new class of regular expressions. We also prove that the lower and upper bound on the size of the finite-state automaton used for on-line validation is exponential in the size of the DTD. |
