Weighted Picture Automata and Weighted Logics

Authors: Ina Fichtner

Publish Date: 2009/07/23

Volume: 48, Issue: 1, Pages: 48-78

PDF Link

Abstract

We investigate formal power series on pictures These are functions that map pictures to elements of a semiring and provide an extension of twodimensional languages to a quantitative setting We establish a notion of a weighted MSO logics over pictures The semantics of a weighted formula will be a picture series We introduce weighted 2dimensional online tessellation automata W2OTA and prove that for commutative semirings the class of picture series defined by sentences of the weighted logics coincides with the family of picture series that are computable by W2OTA Moreover we show that the family of behaviors of W2OTA coincide precisely with the class of picture series characterized by weighted quadrapolic picture automata and consequently the notion of weighted recognizability presented here is robust However the weighted structures can not be used to get better decidability properties than in the language case For every commutative semiring it is undecidable whether a given MSO formula has restricted structure or whether the semantics of a formula has empty support

Keywords: