Definable transductions and weighted logics for texts |
| |
Authors: | Christian Mathissen |
| |
Affiliation: | Institut für Informatik, Universität Leipzig, 04009 Leipzig, Germany |
| |
Abstract: | A text is a word together with an additional linear order on it. We study quantitative models for texts, i.e. text series which assign to texts elements of a semiring. We introduce an algebraic notion of recognizability following Reutenauer and Bozapalidis as well as weighted automata for texts combining an automaton model of Lodaya and Weil with a model of Ésik and Németh. After that we show that both formalisms describe the text series definable in a certain fragment of weighted logics as introduced by Droste and Gastin. In order to do so, we study certain definable transductions and show that they are compatible with weighted logics. |
| |
Keywords: | Weighted automata Weighted logics Monadic second-order logic MSO-definable transductions Parenthesizing automata Branching automata Recognizable series Texts |
本文献已被 ScienceDirect 等数据库收录! |