Marcella Anselmo ; Maria Madonia - A stronger recognizability condition for two-dimensional languages

dmtcs:599 - Discrete Mathematics & Theoretical Computer Science, July 12, 2013, Vol. 15 no. 2 -
A stronger recognizability condition for two-dimensional languages

Authors: Marcella Anselmo 1; Maria Madonia 2

  • 1 Dipartimento Informatica ed Applicazioni "Renato M. Capocelli"
  • 2 Dipartimento di Matematica e Informatica

The paper presents a condition necessarily satisfied by (tiling system) recognizable two-dimensional languages. The new recognizability condition is compared with all the other ones known in the literature (namely three conditions), once they are put in a uniform setting: they are stated as bounds on the growth of some complexity functions defined for two-dimensional languages. The gaps between such functions are analyzed and examples are shown that asymptotically separate them. Finally the new recognizability condition results to be the strongest one, while the remaining ones are its particular cases. The problem of deciding whether a two-dimensional language is recognizable is here related to the one of estimating the minimal size of finite automata recognizing a sequence of (one-dimensional) string languages.

Volume: Vol. 15 no. 2
Section: Automata, Logic and Semantics
Published on: July 12, 2013
Accepted on: June 9, 2015
Submitted on: February 15, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1007/978-3-642-21493-6_5
  • 10.1007/978-3-642-21493-6_5
Comparing necessary conditions for recognizability of two-dimensional languages

Consultation statistics

This page has been seen 266 times.
This article's PDF has been downloaded 257 times.