Marrying Words and Trees

Summary: Use nested words to unify linear and hierarchical data and define automata that generalize both word and ordered-tree automata. Show finite-state nested-word automata can be exponentially more succinct than tree automata, and pushdown variants subsume both context-free word and context-free tree languages while analysis complexity and closure properties remain analogous to the classical cases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1433
Venue: PODS
Year: 2007
Pagerank: 4.4097486e-05
Overall Rank: 9,011 | 37.32%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Rajeev Alur

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,392	From Regular Expressions to Nested Words: Unifying Languages and Query Execution for Relational and XML Sequences	2010	VLDB	4.7429265e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
13,552	Effective Characterizations of Tree Logics	2008	PODS	-
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
8,754	Efficient Enumeration for Annotated Grammars	2022	PODS	4.456315e-05
12,430	Expressiveness and Complexity of XML Publishing Transducers	2007	PODS	4.1945683e-05
5,296	Running Tree Automata on Probabilistic XML	2009	PODS	5.5802694e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
13,674	Trees, Automata and XML (Invited Tutorial)	2004	PODS	-
5,055	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS	5.7312839e-05
5,870	Query Automata (extended abstract)	1999	PODS	5.2943906e-05
7,497	Stackless Processing of Streamed Trees	2021	PODS	4.7180617e-05