Liebe Nutzerinnen und Nutzer in der Zeit von Montag 22.04. 9:00Uhr bis voraussichtlich Mitwoch 24.04. 9:00Uhr ist JLUpub aufgrund von Wartungsarbeiten nicht erreichbar. Danke für Ihr Verständnis.
Dear users, JLUpub will be unavailable from Monday 22.04. 9:00 a.m. until probably Wednesday 24.04. 9:00 a.m. due to maintenance work. Thank you for your understanding.
On tally languages and generalized interacting automata
| dc.contributor.author | Buchholz, Thomas | |
| dc.contributor.author | Klein, Andreas | |
| dc.contributor.author | Kutrib, Martin | |
| dc.date.accessioned | 2022-09-12T09:38:42Z | |
| dc.date.available | 1999-02-28T23:00:00Z | |
| dc.date.available | 2022-09-12T09:38:42Z | |
| dc.date.issued | 1999 | |
| dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-1383 | |
| dc.identifier.uri | https://jlupub.ub.uni-giessen.de//handle/jlupub/7554 | |
| dc.identifier.uri | http://dx.doi.org/10.22029/jlupub-6988 | |
| dc.description.abstract | Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the wellknown result that each tally language acceptable by a classical oneway cellular automaton (OCA) in realtime 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 nonregular 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. | en |
| dc.language.iso | en | de_DE |
| dc.relation.ispartofseries | IFIG Research Report; 9902 / 1999 | |
| dc.rights | In Copyright | * |
| dc.rights.uri | http://rightsstatements.org/page/InC/1.0/ | * |
| dc.subject.ddc | ddc:004 | de_DE |
| dc.title | On tally languages and generalized interacting automata | en |
| dc.type | workingPaper | de_DE |
| local.affiliation | FB 07 - Mathematik und Informatik, Physik, Geographie | de_DE |
| local.opus.id | 138 | |
| local.opus.institute | Institut für Informatik | de_DE |
| local.opus.fachgebiet | Informatik | de_DE |
Dateien zu dieser Ressource
Das Dokument erscheint in:
Urheberrechtlich geschützt