Running Tree Automata on Probabilistic XML

Summary: Identify a tractable case for evaluating deterministic bottom-up unranked tree automata on probabilistic XML (distributional-node model): an efficient algorithm when transitions are given by deterministic string automata, enabling sampling and MSO query evaluation under schema conformance. Also analyze complexity of attributes, keys/foreign-keys and extend the model to repeated-sampling nodes that further blow up the possible-world space. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1495
Venue: PODS
Year: 2009
Pagerank: 5.5749031e-05
Overall Rank: 5,301 | 63.16%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,284	Probabilistic XML via Markov Chains	2010	VLDB	5.1232186e-05
6,996	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	4.8629707e-05
7,604	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.6944524e-05
12,221	Transducing Markov Sequences	2010	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
572	The Complexity of Query Reliability	1998	PODS	0.00019888988
1,269	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012911894
2,590	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	8.4863884e-05
2,598	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4660607e-05
2,783	ProTDB: Probabilistic Data in XML	2002	VLDB	8.1268718e-05
2,981	Matching Twigs in Probabilistic XML	2007	VLDB	7.7783189e-05
3,592	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9362111e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
6,682	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9596732e-05
8,555	Incorporating Constraints in Probabilistic XML	2008	PODS	4.4893996e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,981	Matching Twigs in Probabilistic XML	2007	VLDB	7.7783189e-05
4,076	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.4657154e-05
13,688	Trees, Automata and XML (Invited Tutorial)	2004	PODS	-
12,223	Certain Answers for XML Queries	2010	PODS	4.1905499e-05
12,137	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.1905499e-05
6,682	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9596732e-05
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
2,862	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	7.9982917e-05
6,284	Probabilistic XML via Markov Chains	2010	VLDB	5.1232186e-05
3,592	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9362111e-05