Simulations over Two-Dimensional On-Line Tessellation Automata

Gérard Cécé 1 Alain Giorgetti 1, 2
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
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 a 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 of a unique maximal autosimulation relation in a given 2OTA and the existence of a unique minimal 2OTA which is simulation equivalent to this given 2OTA, both computable in polynomial time.
Type de document :
Communication dans un congrès
Mauri, Giancarlo and Leporati, Alberto. 15th International Conference on Developments in Language Theory - DLT 2011, Jul 2011, Milan, Italy. Springer, 6795, pp.141--152, 2011, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/y30755j223127602/〉. 〈10.1007/978-3-642-22321-1_13〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00642531
Contributeur : Alain Giorgetti <>
Soumis le : vendredi 18 novembre 2011 - 11:29:52
Dernière modification le : jeudi 15 février 2018 - 08:48:09

Identifiants

Citation

Gérard Cécé, Alain Giorgetti. Simulations over Two-Dimensional On-Line Tessellation Automata. Mauri, Giancarlo and Leporati, Alberto. 15th International Conference on Developments in Language Theory - DLT 2011, Jul 2011, Milan, Italy. Springer, 6795, pp.141--152, 2011, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/y30755j223127602/〉. 〈10.1007/978-3-642-22321-1_13〉. 〈hal-00642531〉

Partager

Métriques

Consultations de la notice

186