The Standard Generalized Markup Language (SGML) and the Extensible Markup Language (XML) allow authors to better transmit the semantics in their documents by explicitly specifying the relevant structures in a document or class of documents by means of document type definitions (DTDs). Several authors proposed to regard DTDs as extended context-free grammars expressed in a notation similar to extended Backus--Naur form. In addition, the SGML standard allows to modify the semantics of content models (the right-hand side of productions) by exceptions. Inclusion exceptions allow named elements to appear anywhere within the content of a content model, and exclusion exceptions preclude named elements from appearing in the content of a content model. Since XML does not allow exceptions, the problem of exception removal has received much interest recently. Motivated by this, Kilpelainen and Wood proved that exceptions do not increase the expressive power of extended context-free grammars and that for each DTD with exceptions, we can obtain a structurally equivalent extended context-free grammar. Since their argument involved an exponential simulation, they also conjectured that an exponential blow-up in the size of the grammar is a necessary devil when purging exceptions away. We prove their conjecture under the most realistic assumption that NP-complete problems do not admit non-uniform polynomial time algorithms. Kilpelainen and Wood also asked whether the parsing problem for extended context-free grammars with exceptions admits efficient algorithmic solution. We show the NP-completeness of the very basic problem: given a string w and a context-free grammar G (not even extended) with exclusion exceptions (no addition exceptions needed), decide whether w belongs to the language generated by G. Our results and arguments suggest that extended context-free grammars do not provide a suitable model of SGML, especially when one is interested in understanding issues related to exceptions
Complexity of Context-free Grammars with Exceptions and the inadequacy of grammars as models for XML and SGML
2001-01-01
Abstract
The Standard Generalized Markup Language (SGML) and the Extensible Markup Language (XML) allow authors to better transmit the semantics in their documents by explicitly specifying the relevant structures in a document or class of documents by means of document type definitions (DTDs). Several authors proposed to regard DTDs as extended context-free grammars expressed in a notation similar to extended Backus--Naur form. In addition, the SGML standard allows to modify the semantics of content models (the right-hand side of productions) by exceptions. Inclusion exceptions allow named elements to appear anywhere within the content of a content model, and exclusion exceptions preclude named elements from appearing in the content of a content model. Since XML does not allow exceptions, the problem of exception removal has received much interest recently. Motivated by this, Kilpelainen and Wood proved that exceptions do not increase the expressive power of extended context-free grammars and that for each DTD with exceptions, we can obtain a structurally equivalent extended context-free grammar. Since their argument involved an exponential simulation, they also conjectured that an exponential blow-up in the size of the grammar is a necessary devil when purging exceptions away. We prove their conjecture under the most realistic assumption that NP-complete problems do not admit non-uniform polynomial time algorithms. Kilpelainen and Wood also asked whether the parsing problem for extended context-free grammars with exceptions admits efficient algorithmic solution. We show the NP-completeness of the very basic problem: given a string w and a context-free grammar G (not even extended) with exclusion exceptions (no addition exceptions needed), decide whether w belongs to the language generated by G. Our results and arguments suggest that extended context-free grammars do not provide a suitable model of SGML, especially when one is interested in understanding issues related to exceptionsI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
