OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Features of XML Languages that Increase Complexity?

Hi Folks,

Does your XML language [1] contain polymorphic elements? Recursive content? Open content? Co-constraints? Internal references?

How do those features impact the complexity [2] of your language?

Clearly if a feature elevates the language's complexity to "recursively enumerable" then you will want to avoid that feature.

Recall that as a language increases in complexity its attack surface increases. For a recursively enumerable language "no amount of programmer or QA effort can expose a comprehensive selection of the language's exploitable vulnerabilities" [3]. In other words, your language and its processing applications cannot be secured.

I am compiling a list of features that may be used in XML languages. The below is a start at a list. I seek your additions to the list.

Once I have compiled a comprehensive list, then I will start assessing the complexity-impact of each feature.  Would you like to help with this?

XML Language Features

1. Polymorphism – an element is polymorphic if it can be substituted by other elements or if its content can be substituted by other content. For example, this <Publication> element is polymorphic: in <Bookstore> each <Publication> may be substituted by <Book> or <Magazine>.

2. Recursion – the content of an element is recursive. For example, this <section> element is recursive: each <section> contains a <title> followed by an optional <section>.

3. Open content – the content of an element is arbitrary content.

4. Internal references – the value of an IDREF attribute must match the value of an ID attribute.

5. Co-constraints – the language imposes a dependency between two or more sets of elements. Examples: (a) Require the number of occurrences of element A equal the number of occurrences of element B. (b) Require the number of occurrences of elements A, B, and C all be equal.

6. Exponentially expanding user-defined entities – the content of an element contains a reference to an exponentially expanding user-defined entity.

What other features could an XML language have that might impact its complexity?


[1] An XML language is the set of XML instance documents that are acceptable. For example, you may define a Bookstore XML language as the set of all instance documents that have Store as the root element and its content is zero or more Book elements. Here is a member of the language:


That document has a Store element containing two Book elements. An XML document that contains three (or four or five or …) Book elements is also a member of the language. A document that contains, say, cellphone elements is not a member of the language.

[2] Complexity of languages: regular < deterministic context-free < non-deterministic context-free < recursive < recursively enumerable

[3] http://www.cs.dartmouth.edu/~sergey/langsec/papers/Sassaman.pdf


[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS