Reconnaissance parallèle des langages rationnels sur automates cellulaires plans

Autor:	Marianne Delorme, Jacques Mazoyer
Rok vydání:	2002
Předmět:	General Computer Science Computer science Humanities Language recognition Theoretical Computer Science Computer Science(all)
Zdroj:	Theoretical Computer Science. 281(1-2):251-289
ISSN:	0304-3975
DOI:	10.1016/s0304-3975(02)00016-6
Popis:	Peu de résultats sont connus sur la puissance de calcul des automates cellulaires 2D. Dans l'approche “reconnaissance de langages”, la difficulté provient de la multiplicité des plongements possibles d'un mot sur le plan discret. Une question très simple comme la reconnaisance des langages rationnels en temps réel devient vraiment délicate. Nous montrons ce résultat sur deux plongements particuliers (spirale d'Archimède et fil de Hilbert). Cette première investigation met en évidence que ce qui est difficile est moins l'algorithmique que la nature du plan discret.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bd46c5fbd2bab05016f72fe4ff57c459 Zobrazit plný text záznamu Full Text from ScienceDirect