Average stack cost of Büchi pushdown automata

DOI10.4230/LIPICS.FSTTCS.2017.42MaRDI QIDQ5136334zbMATH OpenOpenAlexFDO

Authors Jakub Michaliszyn, Jan Otop

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1710.04490

zbMATH Keywords

pushdown automataaverage stack costweighted pushdown systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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 generalizes mean-payoff objective and can be used 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.

Recommendations

• Computing optimal reachability costs in priced dense-timed pushdown automata
• The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems
• scientific article; zbMATH DE number 1670780
• Mean-payoff pushdown games
• On boundedness problems for pushdown vector addition systems

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Average-energy games
• Mean-payoff pushdown games
• Nested weighted automata
• Nested weighted automata
• Program Analysis Using Weighted Pushdown Systems
• Quantitative languages
• Weighted Pushdown Systems with Indexed Weight Domains
• Weighted pushdown systems and their application to interprocedural dataflow analysis

Cited in

(2)

• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• Long-Run Average Behavior of Vector Addition Systems with States

This page was built for publication: Average stack cost of Büchi pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136334)