We study the decision properties of XML languages. It was known that given a context-free language included in the Dyck language with sufficiently many pairs of parentheses, it is undecidable whether or not it is an XML language. We improve on this result by showing that the problem remains undecidable when the language is written on a unique pair of parentheses. We also prove that if the given language is deterministic, then the problem is decidable; while establishing whether its surfaces are regular turns out to be undecidable whenever the deterministic language is contained in the Dyck language with two pairs of parentheses. Our results are based on a “pumping property” of what Boasson and Berstel call the surface of a context-free language.
Context-free grammars and XML languages / A. Bertoni, C. Choffrut, B. Palano - In: Developments in language theory / [a cura di] O.H. Ibarra, Z. Dang. - Berlin : Springer, 2006. - ISBN 9783540354284. - pp. 108-119 (( Intervento presentato al 10. convegno International Conference on Developments in Language Theory tenutosi a Santa Barbara nel 2006.
Context-free grammars and XML languages
A. BertoniPrimo
;B. PalanoUltimo
2006
Abstract
We study the decision properties of XML languages. It was known that given a context-free language included in the Dyck language with sufficiently many pairs of parentheses, it is undecidable whether or not it is an XML language. We improve on this result by showing that the problem remains undecidable when the language is written on a unique pair of parentheses. We also prove that if the given language is deterministic, then the problem is decidable; while establishing whether its surfaces are regular turns out to be undecidable whenever the deterministic language is contained in the Dyck language with two pairs of parentheses. Our results are based on a “pumping property” of what Boasson and Berstel call the surface of a context-free language.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
512.62 kB
Formato
Adobe PDF
|
512.62 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.