Refining the Hierarchy of Blind Multicounter Languages
Jantzen, Matthias ; Kurganskyy, Aleksej N.
| URL | http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/51/ |
|---|---|
| Dokumentart: | Report (Bericht) |
| Schriftenreihe: | Berichte des Fachbereichs Informatik der Universität Hamburg |
| Bandnummer: | 229 |
| Sprache: | Englisch |
| Erstellungsjahr: | 2001 |
| Publikationsdatum: | 27.08.2009 |
| SWD-Schlagwörter: | Formale Sprache |
| Freie Schlagwörter (Deutsch): | formale Sprachen |
| Freie Schlagwörter (Englisch): | blind multicounter languages , formal languages |
| DDC-Sachgruppe: | Informatik |
| BK - Klassifikation: | 54.10 |
Kurzfassung auf Englisch:
We show that the families (k,r)-RBC of languages accepted (in quasi-realtime) by one-way counter automata having k blind counters of which r are reversal-bounded form a strict and linear hierarchy of semi-AFLs. This hierarchy comprises the families BLIND of blind multicounter languages and RBC of reversal-bounded multicounter languages . This generalizes and sharpens the known results. The proof for the strict inclusions for the first time uses techniques from linear algebra.
Kurzfassung auf Deutsch:
Wir zeigen, dass die Familien (k, r)–RBC der Sprachen, die in Quasi-Realzeit von Z¨ahlerautomaten mit k blinden und r umkehrbeschr¨ankten Z¨ahlern akzeptiert werden, eine echte und lineare Hierarchie von Sprachfamilien bildet. Diese Hierarchie enthält sowohl die bekannte Sprachfamilie BLIND = M∩(C1) der blinden Mehrzählersprachen mit Generatormenge C1 := {w ∈ {a1, b1}∗ | |w|a1 = |w|b1}, als auch die Familie RBC = M∩(B1) der umkehrbeschränkten Mehrzählersprachen. Mit diesem Resultat werden die bekannten Ergebnisse von Greibach, [Grei 78], und Jantzen, [Jant 98], verschärft und verallgemeinert. Die hier benutzte Methode verwendet erstmalig Resultate der linearen Algebra.
Hinweis zum Urherberrecht
Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:
Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.
Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.