Han, Yo-Sub Wood, Derick 2024-01-20T22:35:40Z 2024-01-20T22:35:40Z 2021-09-03 2008-09 0890-5401 https://pubs.kist.re.kr/handle/201004/133184 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. (C) 2008 Elsevier Inc. All rights reserved. English ACADEMIC PRESS INC ELSEVIER SCIENCE AUTOMATA Generalizations of 1-deterministic regular languages Article 10.1016/j.ic.2008.03.013 1 INFORMATION AND COMPUTATION, v.206, no.9-10, pp.1117 - 1125 INFORMATION AND COMPUTATION 206 9-10 1117 1125 scie scopus 000259251400011 2-s2.0-50349091522 Computer Science, Theory & Methods Mathematics, Applied Computer Science Mathematics Article; Proceedings Paper AUTOMATA one-unambiguous regular languages k-lookahead determinism k-block determinism