FOUNDATIONS OF MARKUP, HTML, AND SGML

The Standard Generalized Markup Language (SGML) is a meta-syntactic language for the definition of Document Type Definitions (DTDs), which are, essentially, extended context-free grammars in which the right-hand sides of productions are similar to regular expressions and are called Content Models. Anne Brueggemann-Klein and I began investigating SGML in the early nineties; it led to a number of publications about ambiguity, in the SGML sense, for content models.

In addition, with Darrell Raymond and Frank Tompa we attempted to address the issue of what is markup and what are appropriate meta-semantics for SGML.

Pekka Kilpelainen, Helen Cameron, and Chris Cleverley and I are currently examining the issues of exceptions and their expressive power, the decidability of structural equivalence of DTDs, and how tag minimization can be defined in a general way.

  • [Refereed Journal Articles:]
    1. A. Brueggemann-Klein. Regular expressions into finite automata. Theoretical Computer Science, 120:197-213, 1993.
    2. D.R. Raymond, F.W. Tompa, and D. Wood, From data representation to data model: Meta-Semantic issues in the Evolution of SGML, Computer Standards & Interfaces, 18:25-36, 1996. Also appeared as Technical Report HKUST-CS95-32.
    3. A. Brueggemann-Klein and D. Wood, One-unambiguous regular languages, Information and Computation, (1997), 24 pages, to appear.
    4. A. Brueggemann-Klein and D. Wood, The validation of SGML content models, Mathematical and Computer Modelling, 25:73-84, 1997.
    5. A. Brueggemann-Klein. Compiler-construction tools and techniques for SGML parsers: Difficulties and solutions, Electronic Publishing--Origination, Dissemination and Design, (1996), to appear.

  • [Refereed Conference Presentations:]
    1. A. Brueggemann-Klein and D. Wood, On deterministic regular languages, Proceedings of STACS 92, Springer-Verlag Lecture Notes in Computer Science 577, (1992), 173-184.
    2. A. Brueggemann-Klein, Regular expressions into finite automata, in I.~Simon, editor, Latin 92, Springer-Verlag Lecture Notes in Computer Science 583, (1992), 87-98.
    3. D. R. Raymond, D.R., and Tompa, F.W.T., and D. Wood, Markup reconsidered, Workshop on Principles of Document Processing, (1992), 9 pages.
    4. A. Brueggemann-Klein and D. Wood, The validation of SGML content models, Workshop on Principles of Document Processing, (1992), 6 pages.
    5. A. Brueggemann-Klein, Unambiguity of extended regular expressions in SGML document grammars, in Th. Lengauer, editor, Algorithms--ESA 93, Springer-Verlag Lecture Notes in Computer Science 726, (1993), 73-84.

  • [Books and Chapters in Books:]
    1. D. Wood, Standard Generalized Markup Language: Mathematical and philosophical issues, in Computer Science Today, edited by Jan van Leeuwen (New York, NY: Springer-Verlag Lecture Notes in Computer Science 1000, 1995), 344-365.

  • [Submissions:]
    1. P. Kilpelainen and D. Wood, Exceptions in SGML document grammars, (1996), 30 pages. Also appeared as Technical Report HKUST-CS95-??.
    2. P. Kilpelainen and D. Wood, SGML and Exceptions, (1996), 13 pages. Also appeared as Technical Report HKUST-CS95-??.
    3. H. A. Cameron and D. Wood, Structural equivalence of regular extended context-free grammars and SGML DTDs, in preparation, 1996.

  • [Theses:]
    1. A. Brueggemann-Klein, Formal models in document processing, Habilitationsschrift, Fakultaet Mathematik, Universitaet Freiburg, 1993.
  • [Miscellaneous publications:]
    1. D. R. Raymond, F. W. T. Tompa, and D. Wood, Markup reconsidered, Department of Computer Science, University of Waterloo, Research Report CS-92-??, 1992, and Department of Computer Science, University of Western Ontario, Technical Report 356, 1992.

    • dwood@cs.ust.hk
    Fax: Attn. Derick Wood, 852-2358-1477
    http://www.cs.ust.hk/~dwood/.convexity
    dwood@cs.ust.hk
    Computer Science Department
    The Hong Kong University of Science and Technology
    Clear Water Bay, Kowloon
    HONG KONG