publication . Preprint . 2014

Undecidability of model-checking branching-time properties of stateless probabilistic pushdown process

Lin, Tianrong;
Open Access English
  • Published: 19 May 2014
Abstract
Comment: Author's comments on referee's report added, Interesting
Subjects
arXiv: Computer Science::Formal Languages and Automata TheoryComputer Science::Logic in Computer Science
ACM Computing Classification System: TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
free text keywords: Computer Science - Logic in Computer Science, Computer Science - Formal Languages and Automata Theory, F.4.1
Download from
31 references, page 1 of 3

[1] E.M. Clarke, O. Grumberg and D.A. Peled, Model Checking, MIT Press, 1999.

[2] A.N. Shiryaev, Probability, (Second Edition), Springer-Verlag, New York, 1995.

[3] T. Bra´zdil, Verification of probabilistic recursive sequential programs, PhD thesis, Masaryk University, Faculty of Informatics, 2007.

[4] T. Bra´zdil, V. Broˇzek, V. Forejt and A. Kuˇcera, Branching-time model-checking of probabilistic pushdown automata, Journal of Computer and System Sciences 80 (2014) 139-156.

[5] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

[6] E.L. Post, A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society 52, 1946, pp. 264-268. [OpenAIRE]

[7] C. Baier and J.P. Katoen, Principles of Model Checking, MIT Press, 2008.

[8] S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966.

[9] M.O. Rabin, Probabilistic Automata, Information and Control 6, 1963, pp. 230-245.

[10] S. Arora and B. Barak, Computational Complexity-A Modern Approach, Cambridge University Press, 2009.

[11] O. Kupferman, N. Piterman, and M.Y. Vardi, Pushdown Specifications, Lecture Notes in Artificial Intelligence, Vol. 2541, 2002, pp. 262-277.

[12] H. Hansson and B. Jonsson, A logic for reasoning about time and reliability, Formal Aspects of Computing 6 (1994) 512-535.

[13] M. Lo`eve, Probability Theory I (4th edtion), Springer-Verlag, New York, 1978.

[14] M. Lo`eve, Probability Theory II (4th edtion), Springer-Verlag, New York, 1978.

[15] J. Esparza, A. Kuˇcera and R. Mayr, Model-checking probabilistic pushdown automata, Logical Methods in Computer Science Vol. 2 (1:2) 2006, pp. 1-31. [OpenAIRE]

31 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue