Geodesic
On $\omega$-languages of special billiards
Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 95-108.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider non-deterministic initial finite automata without final states and the $\omega$-languages determined by such automata. For such $\omega$-languages, we consider the so-called languages of obstructions. We define and analyse billiard $\omega$-languages determined in a special way for each $n\ge 3$ over an alphabet consisting of $n$ letters. Each $\omega$-word of such $\omega$-language can be obtained with the use of infinite number of reflections of a point from the cushions of billiards having the form of a regular $n$-polygon. For such $\omega$-languages, we consider the languages of obstructions and show that for any $n$ a language of obstructions is not regular. The research was supported by the Russian Foundation for Basic Research, grants 99–01–00907 and 00–15–99253. 
@article{DM_2002_14_3_a9,
     author = {B. Melnikov},
     title = {On $\omega$-languages of special billiards},
     journal = {Diskretnaya Matematika},
     pages = {95--108},
     publisher = {mathdoc},
     volume = {14},
     number = {3},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_3_a9/}
}
TY  - JOUR
AU  - B. Melnikov
TI  - On $\omega$-languages of special billiards
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 95
EP  - 108
VL  - 14
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_3_a9/
LA  - ru
ID  - DM_2002_14_3_a9
ER  - 
%0 Journal Article
%A B. Melnikov
%T On $\omega$-languages of special billiards
%J Diskretnaya Matematika
%D 2002
%P 95-108
%V 14
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2002_14_3_a9/
%G ru
%F DM_2002_14_3_a9
B. Melnikov. On $\omega$-languages of special billiards. Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 95-108. http://geodesic.mathdoc.fr/item/DM_2002_14_3_a9/

[1] Eilenberg S., Automata, languages and machines, Academic Press, New York, 1974 | MR | Zbl

[2] Salomaa A., Zhemchuzhiny teorii formalnykh yazykov, Mir, Moskva, 1986 | MR

[3] Thomas W., “Automata on infinite objects”, Formal models and semantics. Handbook of theoretical computer science, eds. Van Leeuwen, J., Ed. V. B. Elsevier, Amsterdam, 1990, 133–191 | MR | Zbl

[4] Staiger L., “$\omega$-Languages”, Handbook of formal languages, 3, Springer, Berlin, 1997, 339–387 | MR

[5] Brauer V., “Vvedenie v teoriyu konechnykh avtomatov”, Radio i svyaz, 1987, Moskva | MR

[6] Melnikov B., “$2\omega$-finite automata and sets of obstructions of their languages”, Korean J. Comput. Applied Math., 6:3 (1999), 565–574 | MR | Zbl

[7] Bergman G. M., “The diamond lemma for ring theory”, Adv. Math., 29 (1978), 178–218 | DOI | MR | Zbl

[8] Ufnarovskii V., “Kombinatornye i asimptoticheskie metody v algebre”, Itogi nauki i tekhniki. Sovremennye problemy matematiki, fundamentalnye napravleniya, 57, VINITI, Moskva, 1990, 5–177 | MR

[9] Belov A., Borisenko V., Latyshev V., “Monomial algebras”, J. Math. Sci., 87:3 (1997), 3463–3575 | DOI | MR | Zbl

[10] Trakhtenbrot B. A., Bardzin Ya. M., Konechnye avtomaty: povedenie i sintez, Nauka, Moskva, 1970 | MR

[11] Staiger L., “Finite-state $\omega$-languages”, J. CSS, 27 (1983), 434–448 | MR | Zbl

[12] Beal M. P., “Minimal forbidden words and symbolic dynamics”, Proc. STACS'96, 555–566 | MR

[13] Maler O., Staiger L., “On syntactic congruences for $\omega$-languages”, TCS, 183 (1997), 93–112 | DOI | MR | Zbl

[14] Mignosi F., “Forbidden factors in finite and infinite words”, Jewels are Forever, Springer, Berlin, 1999, 339–350 | MR | Zbl

[15] Perrin D., “Finite automata”, Formal models and semantics. Handbook of theoretical computer science, ed. J. van Leeuwen, Elsevier, Amsterdam, 1990, 1–57 | MR | Zbl

[16] Cohen R. S., Gold Y., “Theory of $\omega$-languages. I”, Characterizations of $\omega$-context-free languages, 15 (1977), 169–184 | MR | Zbl

[17] Akho A., Ulman Dzh., Teoriya sintaksicheskogo analiza, perevoda i kompilyatsii, t. 1, Mir, Moskva, 1978

[18] Melnikov B., Vakhitova A., “Some more on the finite automata”, Korean J. Comput. Applied Math., 5:3 (1998), 495–506 | MR

[19] Melnikov B., Melnikova A., “Some properties of the basis finite automaton”, Korean J. Comput. Applied Math., 9:1 (2002), 131–150 | MR

[20] Melnikov B., Sciarini-Guryanova N., Possible edges of a finite automaton defining the given regular language, Korean J. Comput. Applied Math., 9, no. 3, 2002 | MR

[21] Bridson M., Gilman R., “Formal language theory and the geometry of 3-manifolds”, Comment. Math. Helv., 71:4 (1996), 525–555 | DOI | MR | Zbl