Geodesic
Periodic properties of pushdown automata
Diskretnaya Matematika, Tome 30 (2018) no. 3, pp. 40-47
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Finite automata transform periodic sequences into periodic ones. The period of the output sequence is bounded from above by a linear function of input period. It is known that pushdown automata also preserve the set of periodic sequences. We prove that the output period for one-counter pushdown automata is bounded from above by a quadratic function of input period. We also give an example of an automaton with a quadratic lower bound on output period.
Keywords: pushdown automaton, one-counter pushdown automaton, periodic sequence. 
@article{DM_2018_30_3_a3,
     author = {I. E. Ivanov},
     title = {Periodic properties of pushdown automata},
     journal = {Diskretnaya Matematika},
     pages = {40--47},
     year = {2018},
     volume = {30},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2018_30_3_a3/}
}
TY  - JOUR
AU  - I. E. Ivanov
TI  - Periodic properties of pushdown automata
JO  - Diskretnaya Matematika
PY  - 2018
SP  - 40
EP  - 47
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2018_30_3_a3/
LA  - ru
ID  - DM_2018_30_3_a3
ER  - 
%0 Journal Article
%A I. E. Ivanov
%T Periodic properties of pushdown automata
%J Diskretnaya Matematika
%D 2018
%P 40-47
%V 30
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2018_30_3_a3/
%G ru
%F DM_2018_30_3_a3
I. E. Ivanov. Periodic properties of pushdown automata. Diskretnaya Matematika, Tome 30 (2018) no. 3, pp. 40-47. http://geodesic.mathdoc.fr/item/DM_2018_30_3_a3/

[1] Oettinger A., “Automatic syntactic analysis and the pushdown store”, Structure of Language and its Mathematical Concepts, Proc. 12th Symp. Appl. Math., 1961, 104–129 | DOI

[2] Schutzenberger M. P., “On contex-free languages and pushdown automata”, Inf. and Control, 6:3 (1963), 246–264 | DOI | MR

[3] Chomsky N., “Context-free grammars and pushdown storage”, Quart. Progr. Rep., Res. Lab. Electronics, M.I.T., 65, Princeton, New Jersey, 1962

[4] Evey R.J., “Applications of pushdown-store machines”, Proc. AFIPS Fall Joint Computer Conf., 24, 1963, 215–227 | Zbl

[5] Ginsburg S., Rose G.F., “Some recursively unsolvable problems in ALGOL-like languages”, J. ACM, 10 (1963), 175–195 | DOI | MR | Zbl

[6] Senizergues G., “The equivalence problem for deterministic pushdown automata is decidable”, Proc. ICALP 97, Lect. Notes Comput. Sci., 1256, Springer, Berlin, 1997, 671–681 | DOI | MR | Zbl

[7] Kudryavtsev V.B., Aleshin S.V., Podkolzin A.S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR

[8] Babin D.N., “O polnote dvukhmestnykh o.d.-funktsii otnositelno superpozitsii”, Diskret. matem., 1:4 (1989), 86–91 ; Babin D. N., “On completeness of the binary boundedly determined functions with respect to superposition”, Discrete Math. Appl., 1:4 (1991), 423–431 | MR | Zbl | DOI

[9] Letunovskii A.A., “Tsiklovye indeksy avtomata”, Diskret. matem., 25:4 (2013), 24–29 | DOI | MR | Zbl

[10] Wolfgang Coy, “Automata in Labyrinths”, Int. Conf. Fundamental. Comput. Theor., Lect. Notes Comput. Sci., 56, 1977, 65–71 | DOI | MR | Zbl