The Complexity of Mean-Payoff Automaton Expression

DOI10.1007/978-3-642-31585-5_36MaRDI QIDQ3167028zbMATH OpenOpenAlexFDO

Authors Yaron Velner

Publication date 1 November 2012

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31585-5_36

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Mean-payoff automaton expressions
• Complexity of automata evaluating formulas
• On the complexity of automatic complexity
• On the average complexity of partial derivative automata for semi-extended expressions
• The complexity of interacting automata
• DNA Computing
• On the computational complexity of P automata
• Complexity of some problems from the theory of automata
• A complexity measure on Büchi automata
• Exact complexity of problems of incompletely specified automata

Cited in

(5)

• Faster algorithms for quantitative verification in bounded treewidth graphs
• Hyperplane separation technique for multidimensional mean-payoff games
• Temporal specifications with accumulative values
• Mean-payoff automaton expressions
• On Omega-Languages Defined by Mean-Payoff Conditions

This page was built for publication: The Complexity of Mean-Payoff Automaton Expression

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