Effective Characterizations of Tree Logics

Summary: Survey of algorithmic effective characterizations that decide, given a tree automaton, whether its recognized language is definable in a target tree logic. Covers path-/frontier-testable languages, fragments of Core XPath and MSO, giving automata-theoretic criteria and decidability results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1445
Venue: PODS
Year: 2008
Pagerank: -
Overall Rank: 13,752 | 5.65%
DOI: 10.1145/1376916.1376925

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mikołaj Bojańczyk (University of Warsaw)

BibTeX Citation

@inproceedings{bojanczyk_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Effective Characterizations of Tree Logics}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376925},
        doi = {10.1145/1376916.1376925},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bojańczyk, Mikołaj},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
1	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
2	6,661	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS
3	13,875	Trees, Automata and XML (Invited Tutorial)	2004	PODS
4	5,579	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS
5	6,318	Query Automata (extended abstract)	1999	PODS
6	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
7	4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
8	13,785	Monadic Datalog over Finite Structures with Bounded Treewidth	2007	PODS
9	6,442	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
10	2,969	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS