Generalizations of 1-deterministic regular languages

We examine two generalizations of 1-deterministic regular languages that are used for the content models of DTDs in XML. They are k-lookahead determinism and k-block-determinism. The k-lookahead determinism uses the first k symbols w 1 w 2 ⋯ w k of the current input string as lookahead to process the first symbol w 1. On the other hand, the k-block-determinism takes k w 1 w 2 ⋯ w k as lookahead and process the whole k symbols. We show that there is a hierarchy in k-lookahead determinism and there is a proper hierarchy in k-block-determinism. Moreover, we prove that k-block-deterministic regular languages are a proper subfamily of deterministic k-lookahead regular languages.

Authors

• Yo-Sub Han
• Derick Wood

Keywords

• One-unambiguous regular languages
• k-lookahead determinism
• k-block determinism