A logical approach to locality in pictures languages

作者：

Highlights：

• The class of recognizable picture languages is characterized by existential monadic second-order logic.

• Logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata.

• This shows the logics involved can be made “local” with respect to the underlying regular structures.

• Hierarchy results among some logical frameworks are deduced from the above.

摘要

•The class of recognizable picture languages is characterized by existential monadic second-order logic.•Logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata.•This shows the logics involved can be made “local” with respect to the underlying regular structures.•Hierarchy results among some logical frameworks are deduced from the above.

论文关键词：Picture languages,Locality and tiling,Recognizability,Linear time,Cellular automata,Logical characterizations,Monadic second-order logic,Existential second-order logic

论文评审过程：Received 26 July 2012, Revised 6 May 2015, Accepted 22 January 2016, Available online 9 March 2016, Version of Record 10 June 2016.

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