Review on Deterministic Languages

With the development of network applications, XML has become more and more important. In general, the structures of XML documents are specified by schema languages, e.g., DTD and XML Schema. In this paper, the definition of deterministic regular expressions was introduced and an overview of current research was provided. At first, the definition of deterministic regular expressions and some relative notations were given. Next, some algorithms checking determinism of regular expressions were presented in details. Then, some results about deciding, learning, approximating deterministic languages were shown. Finally, some other relative topics were discussed.