A Nivat theorem for weighted picture automata and weighted MSO logics

作者：

Highlights：

• We define a weighted automaton model taking weights from a new weight structure called picture valuation monoids.

• We prove a Nivat-like theorem for the behavior of this weighted automaton model.

• We introduce the weighted monadic second-order logics which can model average density of pictures.

• We show that a suitable fragment of our logic and our weighted automaton model are expressively equivalent.

摘要

•We define a weighted automaton model taking weights from a new weight structure called picture valuation monoids.•We prove a Nivat-like theorem for the behavior of this weighted automaton model.•We introduce the weighted monadic second-order logics which can model average density of pictures.•We show that a suitable fragment of our logic and our weighted automaton model are expressively equivalent.

论文关键词：Picture valuation monoids,Weighted two-dimensional on-line tessellation automata,Picture series,Nivat's theorem,Weighted logic,Average behavior

论文评审过程：Received 4 July 2015, Revised 22 December 2016, Accepted 19 February 2017, Available online 16 March 2017, Version of Record 6 June 2019.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.02.009