On the complexity of monitoring Orchids signatures, and recurrence equations

DOI10.1007/S10703-017-0303-XzbMATH Open1394.68180OpenAlexW2766982626MaRDI QIDQ1667643FDOQ1667643

Authors Jean Goubault-Larrecq, Jean-Philippe Lachance 

Publication date 30 August 2018

Published in Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10703-017-0303-x

zbMATH Keywords

complexityrecurrence equationsstrongly connected componentsmonitorTarjan's algorithm

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Asymptotic enumeration (05A16) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• On the complexity of determinizing monitors
• A computable version of the random signs problem and Kolmogorov complexity
• On computing signatures of coherent systems
• Nondeterministic seedless oritatami systems and hardness of testing their equivalence
• Nondeterministic seedless oritatami systems and hardness of testing their equivalence
• Short Signatures in the Random Oracle Model
• A complexity dichotomy for partition functions with mixed signs
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• On the complexity of recurring sequences

Cites work

• Analytic combinatorics
• Closed-form upper bounds in static cost analysis
• Computer Aided Verification
• Depth-First Search and Linear Graph Algorithms
• Monitoring metric first-order temporal properties
• Resource analysis of complex programs with cost equations

Cited in

(2)

• Introduction to the special issue on runtime verification
• Computer Aided Verification

Describes a project that uses

Uses Software

• Orchids

This page was built for publication: On the complexity of monitoring Orchids signatures, and recurrence equations

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