Weighted Logics for Unranked Tree Automata |
| |
Authors: | Manfred Droste Heiko Vogler |
| |
Affiliation: | 1.Institute of Computer Science,Leipzig University,Leipzig,Germany;2.Department of Computer Science,Technische Universit?t Dresden,Dresden,Germany |
| |
Abstract: | We define a weighted monadic second order logic for unranked trees and the concept of weighted unranked tree automata, and we investigate the expressive power of these two concepts. We show that weighted tree automata and a syntactically restricted weighted MSO-logic have the same expressive power in case the semiring is commutative or in case we deal only with ranked trees, but, surprisingly, not in general. This demonstrates a crucial difference between the theories of ranked trees and unranked trees in the weighted case. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|