|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/737
|
| Title: | Regularly extended two-way nondeterministic tree automata |
| Authors: | Brüggemann-Klein, Anne
Wood, Derick |
| Keywords: | Tree automata
XML
Caterpillar expressions |
| Issue Date: | 17-Jul-2000 |
| Citation: | Automata Implementation : CIAA 2000, Springer-Verlag Lecture Notes in Computer Science 2088, (2001), 57-66 |
| Series/Report no.: | HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2000-07 |
| Abstract: | We establish that regularly extended two-way nondeterministic tree automata with unranked alphabets have the same expressive power as regularly extended nondeterministic tree automata with unranked alphabets. We obtain this result by establishing regularly extended versions of a congruence on trees and of a congruence on, so called, views. Our motivation for the study of these tree models is the Extensible Markup Language (XML), a metalanguage for defining document grammar. Such grammars have regular sets of right-hand sides for their productions and tree automata provide an alternative and useful modeling tool for them. In particular, we believe that they provide a useful computational model for what we call caterpillar expressions. |
| URI: | http://hdl.handle.net/1783.1/737 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 200007.pdf | | 217Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
