6 citations · 10 across the 7 of their papers we have counts for
13 papers
FC-Datalog as a Framework for Efficient String Querying
Owen M. Bell, Joel D. Day, Dominik D. Freydenberger
Core spanners are a class of document spanners that capture the core functionality of IBM's AQL. FC is a logic on strings built around word equations that when extended with constr…
Layered and Staged Monte Carlo Tree Search for SMT Strategy Synthesis
Zhengyang Lu, Stefan Siemer, Piyush Jha +3
Modern SMT solvers, such as Z3, offer user-controllable strategies, enabling users to tailor solving strategies for their unique set of instances, thus dramatically enhancing solve…
A Generic Information Extraction System for String Constraints
Joel D. Day, Adrian Kröger, Mitja Kulczynski +3
String constraint solving, and the underlying theory of word equations, are highly interesting research topics both for practitioners and theoreticians working in the wide area of…
Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
Joel D. Day, Maria Kosche, Florin Manea +1
We consider subsequences with gap constraints, i.e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i.e., the factors of w between the pos…
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…
An SMT Solver for Regular Expressions and Linear Arithmetic over String Length
Murphy Berzish, Mitja Kulczynski, Federico Mora +4
We present a novel length-aware solving algorithm for the quantifier-free first-order theory over regex membership predicate and linear arithmetic over string length. We implement…
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…
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
Katrin Casel, Joel D. Day, Pamela Fleischmann +3
We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two importa…
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…
The Hardness of Solving Simple Word Equations
Joel D. Day, Florin Manea, Dirk Nowotka
We investigate the class of regular-ordered word equations. In such equations, each variable occurs at most once in each side and the order of the variables occurring in both sides…