A stronger recognizability condition for two-dimensional languages

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.139--155
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980763
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:43
Dernière modification le : jeudi 7 septembre 2017 - 01:03:46
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:40:07

Fichier

2113-8176-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980763, version 1

Collections

Citation

Marcella Anselmo, Maria Madonia. A stronger recognizability condition for two-dimensional languages. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.139--155. 〈hal-00980763〉

Partager

Métriques

Consultations de la notice

673

Téléchargements de fichiers

204