Average stack cost of Büchi pushdown automata

DOI10.4230/LIPICS.FSTTCS.2017.42zbMATH Open1491.68100arXiv1710.04490OpenAlexW2963371887MaRDI QIDQ5136334FDOQ5136334

Authors: Jakub Michaliszyn, Jan Otop 

Publication date: 25 November 2020

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.

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

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

zbMATH Keywords

pushdown automataaverage stack costweighted pushdown systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Weighted pushdown systems and their application to interprocedural dataflow analysis
• Quantitative languages
• Nested weighted automata
• Program Analysis Using Weighted Pushdown Systems
• Weighted Pushdown Systems with Indexed Weight Domains
• Average-energy games
• Mean-payoff pushdown games
• Nested weighted automata

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)