Geodesic
Periodic properties of pushdown automata
Diskretnaya Matematika, Tome 30 (2018) no. 3, pp. 40-47

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

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},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2018},
     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
PB  - mathdoc
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
%I mathdoc
%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/