Simple picture processing based on finite automata and regular grammars

作者：

Highlights：

• We study simple automata and regular grammars that can describe picture languages.

• A comparison with well-known mechanisms from the literature is provided.

• Combinatorial and complexity properties of the mentioned models are investigated.

摘要

•We study simple automata and regular grammars that can describe picture languages.•A comparison with well-known mechanisms from the literature is provided.•Combinatorial and complexity properties of the mentioned models are investigated.

论文关键词：Boustrophedon finite automata,Returning finite automata,Picture (array) languages,Regular matrix languages,Array grammars,Isometric and non-isometric arrays,Character recognition,Image processing

论文评审过程：Received 21 October 2016, Revised 16 June 2017, Accepted 11 July 2017, Available online 30 April 2018, Version of Record 30 April 2018.

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