Matthias Jantzen and Alexy Kurganskyy.
Refining the hierarchy of blind multicounter languages.
In Afonso Ferreira and Horst Reichel, editors, Proceedings of
the18th Annual Symposium on Theoretical Aspects of Computer Science (STACS
2001, Dresden, Germany, February 15-17, 2001), volume 2010 of Lecture
Notes in Computer Science, pages 376-387, Berlin, Heidelberg, New York,
2001. Springer-Verlag.
Kurzfassung: Bisher nicht verfügbar.
@inproceedings{Jantzen+01a, Abstract = {We show that the families $(k,r)\mbox{--$\mathit{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 $\mathit{BLIND} = \mathcal{M}_{\cap}({C_1})$ of blind multicounter languages with generator $C_1:=\{w\in\{a_1, b_1\}^*\mid \abs{w}_{a_1} = \abs{w}_{b_1}\}$ and $RBC = \mathcal{M}_{\cap}({B_1})$ of reversal-bounded multicounter languages with generator $B_1 := \{a_1^n b_1^n \mid n\in \N \}$. This generalizes and sharpens the known results from [Greibach 1978] and [Jantzen 1998].}, Address = Springer.addr, Author = {Jantzen, Matthias and Kurganskyy, Alexy}, Booktitle = {Proceedings of the18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001, Dresden, Germany, February 15--17, 2001)}, Editor = {Ferreira, Afonso and Reichel, Horst}, Isbn = {3-540-41695-1}, Pages = {376--387}, Publisher = Springer, Series = LNCS, Title = {Refining the Hierarchy of Blind Multicounter Languages}, Volume = 2010, Year = 2001 }
Diese Informationen werden zur Verfügung gestellt, um technische und Forschungsarbeiten zeitnah bekannt zu geben. Das Urheberrecht und alle damit verbundenen Rechte verbleiben bei den Autoren bzw. anderen Rechteinhabern. Von jedem, der Informationen dieser Seiten übernimmt, wird erwartet, dass er sich an die jeweiligen Bedingungen und Beschränkungen der Rechteinhaber hält. Meist bedeutet dies, dass die hier bereitgestellten Daten nicht ohne explizite Genehmigung der Rechteinhaber weiterveröffentlicht werden dürfen.