Single-Type Approximations of Regular Tree Languages

Speaker(s)

Tomasz Idziaszek

Affiliation

Uniwersytet Warszawski

Date

Jan. 6, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

XML Schema Definitions can be adequately abstracted by the single-type regular tree languages, which form a strict subclass of regular unranked tree languages. Sadly, in this respect, XSDs are not closed under the basic operations of union and set difference, complicating important task in schema integration and evolution. We investigate how these operations can be approximated within the framework of single-type regular tree languages. We consider both lower and upper approximations.

---