
doi: 10.1007/11779148_11
handle: 2434/26971
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. Key Words: context-free grammars, Dyck languages, XML
[INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation
[INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
