Size-Change Abstraction and Max-Plus Automata

DOI10.1007/978-3-662-44522-8_18MaRDI QIDQ2922015zbMATH OpenOpenAlexFDO

Authors Thomas Colcombet, Laure Daviaud, Florian Zuleger

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://openaccess.city.ac.uk/id/eprint/21300/1/main_max_plus.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Max-plus automata
• A contribution to the determinization of max-plus automata
• On the size of logical automata
• Size-change termination and transition invariants
• Bounds on the automata size for Presburger arithmetic
• Compositions of (max,+) automata
• New size hierarchies for two way automata
• Implementation and Application of Automata
• Implementation and Application of Automata
• Size-change termination and satisfiability for linear-time temporal logics

Cited in

(15)

• scientific article; zbMATH DE number 7215283 (Why is no real title available?)
• Comparison of max-plus automata and joint spectral radius of tropical matrices
• A contribution to the determinization of max-plus automata
• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Asymptotically precise ranking functions for deterministic size-change systems
• Simulations and bisimulations for max-plus automata
• Complexity and resource bound analysis of imperative programs using difference constraints
• Reachability analysis for timed automata using max-plus algebra
• Automata and program analysis
• The Shortest Identities for Max-Plus Automata with Two States.
• Max-plus automata
• The factorisation forest theorem
• Type-based analysis of logarithmic amortised complexity
• INDUCTIVE COMPOSITION OF NUMBERS WITH MAXIMUM, MINIMUM, AND ADDITION: A New Theory for Program Execution-Time Analysis
• Compositions of (max,+) automata

This page was built for publication: Size-Change Abstraction and Max-Plus Automata

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