inria-00527077, version 3
Simulations for a Class of Two-Dimensional Automata
Gérard Cécé a, 1Alain Giorgetti
a, 1, 2, 3
N° RR-7425 (2010)
Résumé : 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.
- a – Université de Franche-Comté
- 1 : Laboratoire d'Informatique de Franche-Comté (LIFC)
- Université de Franche-Comté : EA4269
- 2 : CASSIS (INRIA Lorraine - LORIA / LIFC)
- INRIA – CNRS : FRE2661 – Université de Franche-Comté – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- 3 : CASSIS (INRIA Nancy - Grand Est / LORIA / LIFC)
- Université de Lorraine – Université de Franche-Comté – CNRS : FRE2661 – INRIA
- Domaine : Informatique/Théorie et langage formel
- Mots-clés : simulation – tiling – picture languages – picture automata
- Référence interne : RR-7425
- Versions disponibles : v1 (19-10-2010) v2 (29-04-2011) v3 (26-11-2012)
- inria-00527077, version 3
- http://hal.inria.fr/inria-00527077
- oai:hal.inria.fr:inria-00527077
- Contributeur : Alain Giorgetti
- Soumis le : Vendredi 23 Novembre 2012, 13:34:10
- Dernière modification le : Mardi 27 Novembre 2012, 11:00:09
Documents associés
Exporter