Marrying words and trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Marrying words and trees

Full text

Pdf (340 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Beijing, China

SESSION: Sequences, streams, events table of contents

Pages: 233 - 242

Year of Publication: 2007

ISBN:978-1-59593-685-1

Author

Rajeev Alur

University of Pennsylvania

Sponsors

ACM: Association for Computing Machinery
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 102, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1265530.1265564 What is a DOI?

ABSTRACT

Traditionally, data that has both linear and hierarchical structure, such as annotated linguistic data, is modeled using ordered trees and queried using tree automata. In this paper, we argue that nested words and automata over nested words offer a better way to capture and process the dual structure. Nested words generalize both words and ordered trees, and allow both word and tree operations. We study various classes of automata over nested words, and show that while they enjoy expressiveness and succinctness benefits over word and tree automata, their analysis complexity and closure properties are analogous to the corresponding word and tree special cases. In particular, we show that finite-state nested word automata can be exponentially more succinct than tree automata, and pushdown nested word automata include the two incomparable classes of context-free word languages and context-free tree languages.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. Alur, S. Chaudhuri, and P. Madhusudan. Languages of nested trees. In Proc. 18th International Conference on Computer-Aided Verification, LNCS 4144, pages 329--342. Springer, 2006.
	2	R. Alur, V. Kumar, P. Madhusudan, and M. Viswanathan. Congruences for visibly pushdown languages. In Automata, Languages and Programming: Proceedings of the 32nd ICALP, LNCS 3580, pages 1102--1114. Springer, 2005.
	3	Rajeev Alur , P. Madhusudan, Visibly pushdown languages, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007390]
	4	R. Alur and P. Madhusudan. Adding nesting structure to words. In Developments in Language Theory, LNCS 4036, pages 1--13, 2006.
	5	A. Brüggemann-Klein, M. Murata, and D. Wood. Regular tree and regular hedge languages over unranked alphabets: Version 1. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology, 2001.
	6	H. Comon, M. Dauchet, R. Gilleron, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Draft, Available at http://www.grappa.univ-lille3.fr/tata/, 2002.
	7	Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
	8	I. Guessarian. Pushdown tree automata. Mathematical Systems Theory, 16:237--264, 1983.
	9	D. Knuth. A characterization of parenthesis languages. Information and Control, 11(3):269--289, 1967.
	10	V. Kumar, P. Madhusudan, and M. Viswanathan. Minimization, learning, and conformance testing of Boolean programs. In CONCUR'06: 17th International Conference on Concurrency Theory, LNCS 4137, pages 203--217. Springer, 2006.
	11	Viraj Kumar , P. Madhusudan , Mahesh Viswanathan, Visibly pushdown automata for streaming XML, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242714]
	12	Orna Kupferman , Nir Piterman , Moshe Y. Vardi, Pushdown Specifications, Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, p.262-277, October 14-18, 2002
	13	L. Libkin. Logics for unranked trees: An overview. In Automata, Languages and Programming, 32nd International Colloquium, Proceedings, LNCS 3580, pages 35--50. Springer, 2005.
	14	C. Láding, P. Madhusudan, and O. Serre. Visibly pushdown games. In FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 24th International Conference, LNCS 3328, pages 408--420. Springer, 2004.
	15	W. Martens and J. Niehren. Minimizing tree automata for unranked trees. In Proceedings of the 10th International Symposium on Database Programming Languages, pages 233--247, 2005.
	16	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	17	Frank Neven, Automata, Logic, and XML, Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, p.2-26, September 22-25, 2002
	18	T. Schwentick. Automata for XML -- a survey. Technical report, University of Dortmund, 2004.
	19	Wolfgang Thomas, On Logics, Tilings, and Automata, Proceedings of the 18th International Colloquium on Automata, Languages and Programming, p.441-454, July 08-12, 1991