3 citations · 3 across the 3 of their papers we have counts for
7 papers
Formal Languages via Theories over Strings
Joel D. Day, Vijay Ganesh, Nathan Grewal +1
We investigate the properties of formal languages expressible in terms of formulas over quantifier-free theories of word equations, arithmetic over length constraints, and language…
String Theories involving Regular Membership Predicates: From Practice to Theory and Back
Murphy Berzish, Joel D. Day, Vijay Ganesh +4
Widespread use of string solvers in formal analysis of string-heavy programs has led to a growing demand for more efficient and reliable techniques which can be applied in this con…
The Edit Distance to -Subsequence Universality
Pamela Fleischmann, Maria Kosche, Tore Koß +2
A word is a subsequence of another word if can be obtained from by deleting some of its letters. The word with alph is called -subsequence universal i…
On Solving Word Equations Using SAT
Joel D. Day, Thorsten Ehlers, Mitja Kulczynski +3
We present Woorpje, a string solver for bounded word equations (i.e., equations where the length of each variable is upper bounded by a given integer). Our algorithm works by refor…
k-Spectra of weakly-c-Balanced Words
Joel D. Day, Pamela Fleischmann, Florin Manea +1
A word is a scattered factor of if can be obtained from by deleting some of its letters. That is, there exist the (potentially empty) words , and…
The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability
Joel Day, Vijay Ganesh, Paul He +2
The study of word equations (or the existential theory of equations over free monoids) is a central topic in mathematics and theoretical computer science. The problem of deciding w…