On the computation power of finite automata in two-dimensional environments

KURGANSKYY, Oleksiy ; POTAPOV, Igor

In: DLT 2004 : developements in language theory (Auckland, 13-17 December 2004)Lecture notes in computer science :261-271

Konferenz - print, 19 ref

Wie komme ich dran?

In this paper we study the model of a finite state automaton interacting with infinite two-dimensional geometric environments. We show that the reachability problem for a finite state automaton interacting with a quadrant of the plane extended by a power function, a polynomial function or a linear function is algorithmically undecidable, by simulating a Minsky machine. We also consider the environment defined by a parabola which impedes the direct simulation of multiplication. However we show that the model of a finite automaton interacting inside a parabola is also universal.

Titel:	On the computation power of finite automata in two-dimensional environments
Autor/in / Beteiligte Person:	KURGANSKYY, Oleksiy ; POTAPOV, Igor
Link:	View record from PASCAL Archive
Quelle:	DLT 2004 : developements in language theory (Auckland, 13-17 December 2004)Lecture notes in computer science :261-271
Veröffentlichung:	Berlin: Springer, 2004
Medientyp:	Konferenz
Umfang:	print, 19 ref
ISSN:	0302-9743 (print)
Schlagwort:	Control theory, operational research Automatique, recherche opérationnelle Computer science Informatique Sciences exactes et technologie Exact sciences and technology Sciences appliquees Applied sciences Informatique; automatique theorique; systemes Computer science; control theory; systems Informatique théorique Theoretical computing Théorie des langages et analyse syntaxique Language theory and syntactical analysis Atteignabilité Reachability Asequibilidad Automate fini Finite automaton Autómata estado finito Fonction polynomiale Polynomial function Función polinomial Machine état fini Finite state machine Máquina estado finito Modèle 2 dimensions Two dimensional model Modelo 2 dimensiones Modélisation Modeling Modelización Théorie langage Language theory Teoría lenguaje
Sonstiges:	Nachgewiesen in: PASCAL Archive Sprachen: English Original Material: INIST-CNRS Document Type: Conference Paper File Description: text Language: English Author Affiliations: Institute of Applied Mathematics and Mechanics, Ukrainian National Academy of Sciences, Donetsk, Ukraine ; Department of Computer Science, University of Liverpool, Liverpool, United Kingdom Rights: Copyright 2005 INIST-CNRS ; CC BY 4.0 ; Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS Notes: Computer science; theoretical automation; systems

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.