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.5802694e-05
Overall Rank: 5,296 | 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.128131e-05
6,997	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	4.8676446e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05
12,213	Transducing Markov Sequences	2010	PODS	4.1945683e-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.00057857292
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
571	The Complexity of Query Reliability	1998	PODS	0.00019910719
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
2,584	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS	8.4948053e-05
2,594	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.474176e-05
2,774	ProTDB: Probabilistic Data in XML	2002	VLDB	8.134432e-05
2,978	Matching Twigs in Probabilistic XML	2007	VLDB	7.7845728e-05
3,589	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9427709e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
6,681	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9643102e-05
8,558	Incorporating Constraints in Probabilistic XML	2008	PODS	4.4937074e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,978	Matching Twigs in Probabilistic XML	2007	VLDB	7.7845728e-05
4,073	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS	6.4719397e-05
13,674	Trees, Automata and XML (Invited Tutorial)	2004	PODS	-
12,215	Certain Answers for XML Queries	2010	PODS	4.1945683e-05
12,129	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.1945683e-05
6,681	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9643102e-05
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
2,855	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.0059865e-05
6,284	Probabilistic XML via Markov Chains	2010	VLDB	5.128131e-05
3,589	On the Complexity of Managing Probabilistic XML Data	2007	PODS	6.9427709e-05