To Some Structural Properties Of ∞-languages

Ivan Mezník

Abstract


Properties of catenation of sequences of finite (words) and infinite (  lengths are largely studied in formal language theory. These operations are derived from the mechanism how they are accepted or generated by the corresponding devices. Finite automata accept structures containing only words, automata accept only words. Structures containing both words and words (∞ - words) are mostly generated by various types of ∞ - automata(∞- machines). The aim of the paper is to investigate algebraic properties of operations on ∞ - words generated by IGk –automata, where k is to model the depth of memory. It has importance in many applications (shift registers, discrete systems with memory,…). It is shown that resulting algebraic structures are of „pure“ groupoid or partial groupoid type.


Full Text:

PDF

References


J. Chvalina, Š. Hošková-Mayerová, General ω- hyperstructures and certain applications of those, Ratio Mathematica 23, 3-20(2012)

Z. Grodzki, The k – machines, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., Vol. XVIII, 7, 541-544(1970)

M. Juráš and I. Mezník, On IG – languages, Mathematics University of Oulu(1992)

W. Kwasowiec, Generable sets, Information and Control 17, 257-264(1970)

M. Linna, On ω-sets associated with context-free languages, Inform. and Control 31, 273-293(1976)

R. McNaughton, Testing and generating infinite sequences by a finite automaton. Inform. and Control 9, 521-530 (1966)

I. Mezník, On a subclass of ∞ - regular languages, Theoretical Computer Science 61, 25-32(1988)

I. Mezník, On some structural properties of a subclass of ∞ - regular languages, Discrete Applied Mathematics 18, 315-319(1987)

D.E. Muller, Infinite sequences and finite machines, In: IEEE Proc. Fourth Ann. Symp. On Switching Theory and Logical Design, 3-16(1963)

M. Nivat, Infinite words, infinite trees, infinite computations, In: J. W. De Bakker and J. Van Leeuwen, eds., Foundations of Computer Science III (Mathematisch Centrum, Amsterdam), 5-52(1979)

M. Novotný, Sets constructed by acceptors, Inform. and Control 26, 116-133(1974)

Z. Pawlak, Stored program computers. Algorytmy 10, 7-22(1969)

D. Perrin, An introduction to finite automata on infinite words, Lecture Notes in Computer Science 192, 2-17(1984)

A. Skowron, Languages determined by machine systems, , Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., Vol.XIX,4,327-329(1971)

L. Staiger, Finite-state ω – languages, J. of Comp. And Syst. Sci. 27, 434-448(1983)




DOI: http://dx.doi.org/10.23755/rm.v42i0.721

Refbacks

  • There are currently no refbacks.


Copyright (c) 2022 Ivan Mezník

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.