S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.
DOI : 10.1017/CBO9780511804090

C. Baier and J. P. Katoen, Principles of Model Checking, 2009.

P. W. Beame, S. A. Cook, and H. J. Hoover, Log Depth Circuits for Division and Related Problems, SIAM Journal on Computing, vol.15, issue.4, pp.994-1003, 1986.
DOI : 10.1137/0215070

A. Bouajjani, J. Esparza, and O. Maler, Reachability analysis of pushdown automata: Application to modelchecking, Proc. CONCUR'97, pp.135-150, 1997.

L. Bozzelli, Complexity results on branching-time pushdown model checking, Theoretical Computer Science, vol.379, issue.1-2, pp.286-297, 2007.
DOI : 10.1016/j.tcs.2007.03.049

T. Brazdil, V. Brozek, K. Etessami, A. Kucera, and D. Wojtczak, One-Counter Markov Decision Processes, Proc. SODA 2010, pp.863-874, 2010.
DOI : 10.1137/1.9781611973075.70

T. Cachat, Uniform Solution of Parity Games on Prefix-Recognizable Graphs, Electronic Notes in Theoretical Computer Science, vol.68, issue.6, pp.71-84, 2002.
DOI : 10.1016/S1571-0661(04)80534-6
URL : https://hal.archives-ouvertes.fr/hal-00019913

J. Cai and M. Furst, PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS, International Journal of Foundations of Computer Science, vol.02, issue.01, pp.67-76, 1991.
DOI : 10.1142/S0129054191000054

J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon, Efficient Algorithms for Model Checking Pushdown Systems, Proc. CAV 2000, pp.232-247, 2000.
DOI : 10.1007/10722167_20

K. Etessami and M. Yannakakis, Recursive markov decision processes and recursive stochastic games, Proc. ICALP 2005, pp.891-903, 2005.

S. Göller and M. Lohrey, Infinite State Model-Checking of Propositional Dynamic Logics, Proc. CSL 2006, pp.349-364, 2006.
DOI : 10.1007/11874683_23

S. Göller, R. Mayr, and A. W. To, On the Computational Complexity of Verifying One-Counter Processes, 2009 24th Annual IEEE Symposium on Logic In Computer Science, pp.235-244, 2009.
DOI : 10.1109/LICS.2009.37

S. Göller and M. Lohrey, Branching-time model checking of one-counter processes

C. Haase, S. Kreutzer, J. Ouaknine, and J. Worrell, Reachability in Succinct and Parametric One-Counter Automata, Proc. CONCUR'09, pp.369-383, 2009.
DOI : 10.1007/3-540-45061-0_53

U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. W. Wagner, On the power of polynomial time bit-reductions, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pp.200-207, 1993.
DOI : 10.1109/SCT.1993.336526

W. Hesse, E. Allender, and D. A. Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences, vol.65, issue.4, pp.695-716, 2002.
DOI : 10.1016/S0022-0000(02)00025-9

M. Holzer, On emptiness and counting for alternating finite automata, Proc. DLT 1995, pp.88-97, 1996.

P. Jan?ar and Z. Sawa, A note on emptiness for alternating finite automata with a one-letter alphabet, Information Processing Letters, vol.104, issue.5, pp.164-167, 2007.
DOI : 10.1016/j.ipl.2007.06.006

M. Nair, On Chebyshev-Type Inequalities for Primes, The American Mathematical Monthly, vol.89, issue.2, pp.126-129, 1982.
DOI : 10.2307/2320934

N. Piterman and M. Y. Vardi, Global Model-Checking of Infinite-State Systems, Proc. CAV 2004, pp.387-400, 2004.
DOI : 10.1007/978-3-540-27813-9_30

O. Serre, Note on winning positions on pushdown games with ??-regular conditions, Information Processing Letters, vol.85, issue.6, pp.285-291, 2003.
DOI : 10.1016/S0020-0190(02)00445-3
URL : https://hal.archives-ouvertes.fr/hal-00009319

O. Serre, Parity Games Played on Transition Graphs of One-Counter Processes, Proc. FOSSACS 2006, pp.337-351, 2006.
DOI : 10.1007/11690634_23
URL : https://hal.archives-ouvertes.fr/hal-00016665

D. Thérien and T. Wilke, Temporal logic and semidirect products: An effective characterization of the until hierarchy, Proc. FOCS '96, pp.256-263, 1996.

A. W. To, Model Checking FO(R) over One-Counter Processes and beyond, Proc. CSL 2009, pp.485-499, 2009.
DOI : 10.1006/inco.2000.2894
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.302.6746

H. Vollmer, Introduction to Circuit Complexity, 1999.
DOI : 10.1007/978-3-662-03927-4

K. W. Wagner, More complicated questions about maxima and minima, and some closures of NP, Theoretical Computer Science, vol.51, issue.1-2, pp.53-80, 1987.
DOI : 10.1016/0304-3975(87)90049-1

I. Walukiewicz, Model Checking CTL Properties of Pushdown Systems, Proc. FSTTCS 2000, pp.127-138, 2000.
DOI : 10.1007/3-540-44450-5_10

I. Walukiewicz, Pushdown Processes: Games and Model Checking, BRICS Report Series, vol.3, issue.54, pp.234-263, 2001.
DOI : 10.7146/brics.v3i54.20057
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.4162