Towards more efficient methods for solving regular-expression heavy string constraints

DOI10.1016/j.tcs.2022.12.009OpenAlexW4311421541MaRDI QIDQ2680985

Dirk Nowotka, Murphy Berzish, Vijay Ganesh, Mitja Kulczynski, Florin Manea, Joel D. Day, Federico Mora

Publication date: 5 January 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.12.009

zbMATH Keywords

heuristicsregular expressionsSMT solvingstring solvingstring constraintslinear length constraints

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• z3
• JavaScript
• Stranger
• CVC4
• HAMPI
• S3
• Norn
• Z3str3
• Z3str2
• Saner
• StringFuzz
• ZaligVinder

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An SMT solver for regular expressions and linear arithmetic over string length
• Finite automata and unary languages
• Automata-based model counting for string constraints
• The satisfiability of word equations: decidable and undecidable theories
• String theories involving regular membership predicates: from practice to theory and back
• String solving with word equations and transducers: towards a logic for analysing mutation XSS
• A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings
• Path Feasibility Analysis for String-Manipulating Programs
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Chrobak Normal Form Revisited, with Applications
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

This page was built for publication: Towards more efficient methods for solving regular-expression heavy string constraints