Size-Change Abstraction and Max-Plus Automata

DOI10.1007/978-3-662-44522-8_18zbMATH Open1425.68190OpenAlexW80442178MaRDI QIDQ2922015FDOQ2922015

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

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

Mathematics Subject Classification ID

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

Cited In (15)

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

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)