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. Bertoni
Primo
;
B. Palano
Ultimo
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.
Settore INF/01 - Informatica
2006
Book Part (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/26971
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact