2026-07-22T19:23:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8397 2024-03-06T10:42:00Z ddc:004 open_access

Average Stack Cost of Büchi Pushdown Automata Michaliszyn, Jakub Otop, Jan pushdown automata average stack cost weighted pushdown systems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Michaliszyn and Jan Otop 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.42 urn:nbn:de:0030-drops-83971 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.42 eng https://creativecommons.org/licenses/by/3.0/legalcode