Forest Automata formalism

[Reynolds, Gregg]

Thanks to Paul for making the paper available.  I've been working on a
tree query language that has ended up looking much like a forest/tree
regexp language; I had not considered it from the dtd/schema
perspective.  Looks very promising!

FYI:  There is a bibliography of 144 items in "Handbook of Theoretical
Computer Science Part B", Elsevier and MIT Press 1996, Chapter 4
"Automata on Infinite Objects" by Wolfgang Thomas.  Part Two of the
chapter is entitled "Automata on Infinite Trees."  Caveat: very heavy
sledding.  Most of it sails way over my head, but on pages 165-166 there
is a very concise account of tree concatenation etc., which I found
understandable and useful.  You can probably find this in a bookstore if
you're in a major city.

Two other good references:

"Text Algorithms" by Maxime Crochemore and Wojciech Rytter, Oxford 1994

"Algorithms on Strings, Trees, and Sequences: Computer Science and
Computational Biology", by Dan Gusfield, Cambridge U. Press 1997.  Very
cool book.  Excellent and thorough treatment of suffix trees.

- gregg

> -----Original Message-----
> From:	Paul Prescod [SMTP:papresco at technologist.com]
> Sent:	Tuesday, October 20, 1998 10:50 AM
> To:	xml-dev; tigue at oz.net; macherius at darmstadt.gmd.de; Sean Mc Grath
> Subject:	Forest Automata formalism
> 
> Several people have asked me about my paper on Forest Automata.
> Unfortunately, I haven't been able to find time to compile a decent
> bibliography, nor add the code examples I hoped to, but I'm going to
> release it anyhow. There is a partial(?) bibliography on Robin Cover's
> SGML/XML page.
> 
> My paper (sans biblio) can be found at:
> 
> http://www.prescod.net/forest/shorttut
> 
> Forest Automata theory is a formalism for describing SGML/XML
> validation.
> The formalism makes clear some obvious extensions to SGML/XML
> validationand can be used as a source of ideas and answers relating to
> DTD
> parameterization, "data types" (lexical data types),
> validation-in-context, query languages etc.
> 
> Hopefully I will find time or funding to expand this paper eventually,
> because there are many interesting highways and biways that it hints
> at
> but does not explore.
> 
>  Paul Prescod  - http://itrc.uwaterloo.ca/~papresco
> 

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)