Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

On tally languages and generalized interacting automata

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin

Zum Volltext im pdf-Format: Dokument 1.pdf (298 KB)

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-1383

Universität Justus-Liebig-Universit√§t Gie√üen
Institut: Institut f√ľr Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 9902 / 1999
Sprache: Englisch
Erstellungsjahr: 1999
Publikationsdatum: 28.02.1999
Kurzfassung auf Englisch: Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the well­known result that each tally language acceptable by a classical one­way cellular automaton (OCA) in real­time has to be a regular language we will answer the three natural questions 'How much time do we have to provide?' 'How much power do we have to plug in the single cells (i.e., how complex has a single cell to be)?' and 'How can we modify the mode of operation (i.e., how much nondeterminism do we have to add)?' in order to accept non­regular tally languages.
We show the surprising result that for some classes of generalized interacting automata parallelism does not lead to more accepting power than obtained by a single sequential cell. Adding a wee bit of nondeterminism an infinite hierarchy of unary language families can be shown by allowing more and more nondeterminism.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand