Simulations for a Class of Two-Dimensional Automata

Gérard Cécé 1 Alain Giorgetti 1, 2, 3, *
* Auteur correspondant
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We study the notion of simulation over a class of automata which recognize 2D languages (languages of arrays of letters). This class of two-dimensional On-line Tessellation Automata (2OTA) accepts the same class of languages as the class of tiling systems, considered as the natural extension of classical regular word languages to the 2D case. We prove that simulation over 2OTA implies language inclusion. Even if the existence of a simulation relation between two 2OTA is shown to be an NP-complete problem in time, this is an important result since the inclusion problem is undecidable in general in this class of languages. Then we prove the existence in a given 2OTA of a unique maximal autosimulation relation, computable in polynomial time.
Type de document :
Rapport
[Research Report] RR-7425, INRIA. 2010, pp.18
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00527077
Contributeur : Alain Giorgetti <>
Soumis le : vendredi 23 novembre 2012 - 13:34:10
Dernière modification le : jeudi 15 février 2018 - 08:48:14
Document(s) archivé(s) le : dimanche 24 février 2013 - 03:50:56

Fichier

RR-7425.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00527077, version 3

Citation

Gérard Cécé, Alain Giorgetti. Simulations for a Class of Two-Dimensional Automata. [Research Report] RR-7425, INRIA. 2010, pp.18. 〈inria-00527077v3〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

88