Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic
verfasst von : Parvaneh Babari, Manfred Droste
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Picture languages have been intensively investigated by several research groups. In this paper, we define weighted two-dimensional on-line tessellation automata (W2OTA) taking weights from a new weight structure called picture valuation monoid. The behavior of this automaton model is a picture series mapping pictures over an alphabet to a picture valuation monoid. As one of our main results, we prove a Nivat theorem for W2OTA. It shows that recognizable picture series can be obtained precisely as projections of particularly simple unambiguously recognizable series restricted to unambiguous recognizable picture languages. In addition, we introduce a weighted MSO logic which can model average density of pictures. As the other main result of this paper, we show that W2OTA and a suitable fragment of our weighted MSO logics are expressively equivalent.