
The author introduces a weighted MSO logic for defining series of pictures; here a picture is a finite rectangular array of symbols from a given (finite) alphabet. The main results of the paper show that the picture series over any commutative semiring definable by this logic are the same as the series recognized by weighted two-dimensional on-line tessellation automata -- also a new notion introduced here by the author -- and that these series are precisely the series recognizable by the picture automata previously considered in the literature. To achieve this, the formulas of the logic are restricted in a suitable way. Furthermore, the author proves some negative decidability results concerning the new formalisms. For example, it is shown that it is undecidable whether the support of the series defined by a formula is empty, or whether two tessellation automata recognize the same series.
monadic second-order logic, Formal languages and automata, Automata and formal grammars in connection with logical questions, two-dimensional languages, tessellation automata, Algebraic theory of languages and automata, picture series, undecidability, weighted automata, picture automata, weighted logics
monadic second-order logic, Formal languages and automata, Automata and formal grammars in connection with logical questions, two-dimensional languages, tessellation automata, Algebraic theory of languages and automata, picture series, undecidability, weighted automata, picture automata, weighted logics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 29 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
