On the complexity of monitoring Orchids signatures, and recurrence equations

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

Jean-Philippe Lachance, Jean Goubault-Larrecq

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

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

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)

Cites Work

• Analytic combinatorics
• Depth-First Search and Linear Graph Algorithms
• Computer Aided Verification
• Closed-form upper bounds in static cost analysis
• Monitoring metric first-order temporal properties
• Resource Analysis of Complex Programs with Cost Equations

Cited In (2)

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

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)