k-deterministic regular expression
Yo Sub Han
Department of Computer Science
HKUST

Dec 5, 2003
11-11:50 AM
Room 3501, HKUST


Abstract
--------
Content models are introduced in SGML and XML to define document
types. They are regular expressions extended by some new operators. 
One interesting thing in content models is that they require 
unambiguity. It turns out that unambiguity is same as one-determinism
of Brueggemann-Klein and Wood. They study one-deterministic regular
expressions and languages. 

Giammarresi et al. suggest two alternatives to extend one-determinism
and study one-way, block-deterministic regular languages. 
We present the hierarchy existing in block-deterministic regular
languages and look at the other alternative. 
This is joint work with Derick Wood.