Querying linguistic treebanks with monadic second-order logic in linear time

DOI10.1007/s10849-004-2116-8zbMath1067.68154OpenAlexW2063943888MaRDI QIDQ1770837

Stephan Kepser

Publication date: 7 April 2005

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10849-004-2116-8

zbMATH Keywords

monadic second-order logicqueryComplexity theorytreebank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Natural language processing (68T50)

Related Items (2)

Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees

Uses Software

• XQuery
• Penn Treebank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Generalized finite automata theory with an application to a decision problem of second-order logic
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Querying linguistic treebanks with monadic second-order logic in linear time