Which formal language class are XML and JSON with unique keys? I moved this question from stackoverflow where id got no answers. We had a similar question whether JSON is regular:

JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF. However this is only true for JSON as defined in RFC 4329, section 2.2 which does not require uniqueness of object keys (many may not know but {"a":1,"a":2} is valid JSON!). But if you require unique keys in JSON or unique attribute names in XML this cannot be expressed by a context-free grammars. But which is the language class of JSON with unique keys and for well-formed XML (which implies unique attribute names?).

One of the best paper I found on this subject (Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory) explicitly excludes integrity constraints such as keys/keyrefs and uniqueness to be checked on an additional layer. Beside this the subset of XML defined by an XML Schema or by a DTD is context-free. But not the full set of all well-formed XML documents.

I think a nested stack automaton (=indexed language) should be able to parse JSON with unique key constraint. For XML can simlify the question to the language S of all comma-separated lists of unique integers. Does anyone know more, preferably with citations?

P.S: A simple algorithm to decide the languages (beside the context-free part) is based on a good sorting algorithm. Therefore it should be decidable in "linearithmic time" with O(n log n) worst case. I have not found out yet, whether the complexity class is for instance "mildly context-sensitive", or "indexed" but probably something between context-free and context-sensitive (?).

EDIT: Maybe I better reformulate the question for the more theoretical computer scientists. Given the class CFL of all languages that can be expressed by Backus-Naur-Form with repetition (x := a+ $\Leftrightarrow$ x := a | x a). Now what do I gain in computational power if I introduce a "repetition with unique instances" operator ^, so a^ is a sequence of a where each element results in a different sequence of terminals?
Using BNF with your unique-repetition operator, x := S^ says that an x is an instance a of symbol S, optionally followed by an instance b of set S - a, itself optionally followed by an instance c of set S - a - b, and so forth. If |S| is the number of possible S, and is finite, then 2 ^ |S|! - 1 is the number of possible S^.

It's not really meaningful to talk in terms of the computational power of the language being described, since this is about static semantics, in the twilight between syntax and ordinary (dynamic) semantics. The expressive power of the grammar is extended, since it has a formal means of expressing a particular type of input adaptation.

Specifically, it provides a means of accepting a permutation of a subset of a particular set. I don't think there is any existing name for this class of language. It's certainly not context-free, but the context requirement is at least pretty strictly controlled. If you need a term for it, just coin one. I suggest context-respecting for the class of languages that cannot be described by a context-free grammar without additional embedded information about static semantic constraints, which to be fair are vaguely syntactic in spirit.

The most useful application of this particular extension is probably just the ability to introduce unique-key constraints, but it also lets you describe such interesting sets as x := [0-7]^, which matches any octal number of 8 or fewer non-repeated digits. As for the complexity of it, determining whether an element of the set has been seen is no worse than logarithmic, and the frequency of checking is linear in the number of elements matched, so the ^ operator is indeed decidable in worst-case linearithmic time.