Schemas and Formal Language Theory

Although we have had success in proving decidability of equivalence of some classes of schema we have done this without appealing to formal language theory. Interesting questions include:
  1. Are there any schema languages that are not context free?
  2. What is the class of regular/CF schemas?
  3. Can we decide whether the path language is regular/ CF?
  4. If the path language is regular can we decide what it is?
  5. If we know the regular path language of two schemas can we decide equivalence?
Seb's Home Page
Last updated 2007-04-30