Dynamic behavior matching: a complexity analysis and new approximation algorithms

DOI10.1007/978-3-642-22438-6_20MaRDI QIDQ5200029zbMATH OpenOpenAlexFDO

Authors Matt Fredrikson, Mihai Christodorescu, Somesh Jha

Publication date 29 July 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22438-6_20

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Analyzing catastrophic backtracking behavior in practical regular expression matching
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Model Checking Software
• Faster Regular Expression Matching
• On partial state matching

Cites work

• Dynamic behavior matching: a complexity analysis and new approximation algorithms
• Finite state machines for strings over infinite alphabets
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Space/time trade-offs in hash coding with allowable errors
• Term Rewriting and All That
• Theory and Applications of Satisfiability Testing

Cited in

(2)

• scientific article; zbMATH DE number 5547974 (Why is no real title available?)
• Dynamic behavior matching: a complexity analysis and new approximation algorithms

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Dynamic behavior matching: a complexity analysis and new approximation algorithms

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