Average Stack Cost of Büchi Pushdown Automata

Michaliszyn, Jakub; Otop, Jan

doi:10.4230/LIPIcs.FSTTCS.2017.42

File

LIPIcs.FSTTCS.2017.42.pdf

Filesize: 0.52 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2017.42
URN: urn:nbn:de:0030-drops-83971

Author Details

Jakub Michaliszyn

Jan Otop

Cite AsGet BibTex

Jakub Michaliszyn and Jan Otop. Average Stack Cost of Büchi Pushdown Automata. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2017.42

Abstract

We study the average stack cost of Buechi pushdown automata (Buechi PDA). We associate a non-negative price with each stack symbol and define the cost of a stack as the sum of costs of all its elements. We introduce and study the average stack cost problem (ASC), which asks whether there exists an accepting run of a given Buechi PDA such that the long-run average of stack costs is below some given threshold. The ASC problem generalises mean-payoff objective and can be use to express quantitative properties of pushdown systems. In particular, we can compute the average response time using the ASC problem. We show that the ASC problem can be solved in polynomial time.

Keywords

pushdown automata
average stack cost
weighted pushdown systems

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Patricia Bouyer, Nicolas Markey, Mickael Randour, Kim G Larsen, and Simon Laursen. Average-energy games. Acta Informatica, pages 1-37, 2015.
Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM TOCL, 11(4):23, 2010.
Krishnendu Chatterjee, Thomas A. Henzinger, and Jan Otop. Nested weighted automata. In LICS 2015, pages 725-737, 2015.
Krishnendu Chatterjee, Thomas A. Henzinger, and Jan Otop. Bidirectional nested weighted automata. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, volume 85 of LIPIcs, pages 5:1-5:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2017.5.
Krishnendu Chatterjee and Yaron Velner. Mean-payoff pushdown games. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012, pages 195-204. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/LICS.2012.30.
John E. Hopcroft and Jefferey D. Ullman. Introduction to Automata Theory, Languages, and Comput ation. Adison-Wesley Publishing Company, Reading, Massachusets, USA, 1979.
Jakub Michaliszyn and Jan Otop. Average stack cost of buechi pushdown automata. CoRR, abs/1710.04490, 2017. URL: http://arxiv.org/abs/1710.04490.
Yasuhiko Minamide. Weighted pushdown systems with indexed weight domains. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 230-244. Springer, 2013.
Thomas W. Reps, Akash Lal, and Nicholas Kidd. Program analysis using weighted pushdown systems. In Vikraman Arvind and Sanjiva Prasad, editors, FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings, volume 4855 of Lecture Notes in Computer Science, pages 23-51. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-77050-3_4.
Thomas W. Reps, Stefan Schwoon, Somesh Jha, and David Melski. Weighted pushdown systems and their application to interprocedural dataflow analysis. Sci. Comput. Program., 58(1-2):206-263, 2005. URL: http://dx.doi.org/10.1016/j.scico.2005.02.009.