Blind Counter Automata on w-Words

• Autorzy: Fernau H. , Stiebe R.
• Języki publikacji: EN

Abstrakty

EN

This paper generalizes the concept of blind multicounter languages to infinite words. We introduce two different acceptance modes of blind multicounter machines on w-words, called synchrononous and asynchronous acceptance. These acceptance modes are compared with each other and with families of w-languages of the form L=[formula], where Ui, Vi are finitary blind multicounter languages.

Słowa kluczowe

EN

blind counter machines; w-languages; closure properties

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 51--64
• Opis fizyczny: bibliogr. 22 poz.

Twórcy

autor

Fernau H.

autor

Stiebe R.

• Fachbereich IV, Abteilung Informatik, Universität Trier, D-54286 Trier, Germany,

Bibliografia

• [1] Duparc, J., Finkel, O., Ressayre, J.-R: Computer science and the fine structure of Borel sets, Theoretical Computer Science, 257, 2001, 85-105.
• [2] Engelfriet, J., Hoogeboom, H. J.: X-automataon w-words, Theoretical Computer Science, 110, 1993,1-51.
• [3] Fernau, H.: Iterierte Funktionen, Sprachen und Fraktale, Mannheim: Bl-Verlag, 1994.
• [4] Fernau, H.: Valuations, regular expressions, and fractal geometry, Applicable Algebra in Engineering, Communication and Computing, 7(1), 1996, 59-75.
• [5] Fernau, H., Reinhardt, K., Staiger, L.: Decidability of code properties, Developments in Language Theory DLT; Foundations, Applications, and Perspectives (G. Rozenberg, W. Thomas, Eds.), World Scientific, 2000, pages 153-163.
• [6] Fernau, H., Staiger, L.: Valuations and unambiguity of languages, with applications to fractal geometry, Automata, Languages and Programming, 21st International Colloquium, ICALP (S. Abiteboul, E. Shamir, Eds.), Lecture Notes in Computer Science 820, Springer, 1994, pages 11-22.
• [7] Fernau, H., Staiger, L.: Iterated function systems and control languages, Information and Computation, 168, 2001, 125-143.
• [8] Fernau, H., Stiebe, R.: Sequential grammars and automata with valences, Theoretical Computer Science, 276,2002,377-405.
• [9] Fernau, H., Stiebe, R.: Valuated and valence grammars: an algebraic view, Proceedings DLT (W. Kuich, G. Rozenberg, A. Salomaa, Eds.), Lecture Notes in Computer Science 2295, Springer, 2002, pages 281-292.
• [10] Finkel, O.: An effective extension of the Wagner hierarchy to blind counter automata, Computer Science Logic CSL (L. Fribourg, Ed.), Lecture Notes in Computer Science 2142, Springer, 2001, pages 369-383.
• [11] Greibach, S.: Remarks on blind and partially blind one-way multicounter machines, Theoretical Computer Science,!, 1978,311-324.
• [12] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation, Reading (MA): Addison-Wesley, 1979.
• [13] Mauldin, R. D., Williams, S. C: On the Hausdorff dimension of some graphs, Transactions of the American Mathematical Society, 298(2), December 1986,793-803.
• [14] Merzenich, W., Staiger, L.: Fractals, dimension, and formal languages, RAIRO Informatique theorique et Applications/Theoretical Informatics and Applications, 28(3-4), 1994, 361-386.
• [15] Paun, G.: A new generative device: valence grammars, Rev. Roumaine Math. Pures Appi, XXV(6), 1980, 911-924.
• [16] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages (3 volumes), Springer, 1997.
• [17] Staiger, L.: Empty-storage-acceptance of omega-languages, Fundamentals of Computation Theory FCT (M. Karpinski, Ed.), Lecture Notes in Computer Science 56, Springer, 1977, pages 516-521.
• [18] Staiger, L.: Kolmogorov complexity and Hausdorff dimension, Information and Computation (formerly Information and Control), 103, 1993, 159-194.
• [19] Staiger, L.: co-languages, Technical Report 9, Martin-Luther-Universitat Halle-Wittenberg, Fachbereich Mathematik und Informatik, 1997.
• [20] Staiger, L.: Infinite iterated function systems in Cantor space and the Hausdorff measure of w-power languages, International Journal of Foundations of Computer Science, 16, 2005, 787-802.
• [21] Thomas, W.: Automata on infinite objects, in: Handbook of Theoretical Computer Science, Elsevier, 1990, 133-191.
• [22] Vicolov, S.: Hierarchies of valence languages, Developments in Theoretical Computer Science /International Meeting of Young Computer Scientists IMYCS (J. Dassow, A. Kelemenova, Eds.), Gordon and Breach, 1994, pages 191-196.