Can I read Membership Testing for Semantic Regular Expressions on EtoBox?

Membership Testing for Semantic Regular Expressions by Huang, Yifei; Amini, Matin; Glaunec, Alexis Le; Mamouras, Konstantinos; Raghothaman, Mukund is a scholarly article available to read on EtoBox.

What is Membership Testing for Semantic Regular Expressions about?

SMORE (Chen et al., 2023) recently proposed the concept of semantic regular expressions that extend the classical formalism with a primitive to query external oracles such as databases and large language models (LLMs). Such patterns can be used to identify lines of text containing references to semantic concepts such as cities, celebrities, political entities, etc. The focus in their paper was on automatically synthesizing semantic regular expressions from positive and negative examples. In this paper, we study the membership testing problem: First, We present a two-pass NFA-based algorithm to determine whether a string $w$ matches a semantic regular expression (SemRE) $r$ in $O(|r|^2 |w|^2 + |r| |w|^3)$ time, assuming the oracle responds to each query in unit time. In common situations, where oracle queries are not nested, we show that this procedure runs in $O(|r|^2 |w|^2)$ time. Experiments with a prototype implementation of this algorithm validate our theoretical analysis, and show that the procedure massively outperforms a dynamic programming-based baseline, and incurs a $\approx 2 \times$ overhead over the time needed for interaction with the oracle. Next, We establish connec

Author

Huang, Yifei; Amini, Matin; Glaunec, Alexis Le; Mamouras, Konstantinos; Raghothaman, Mukund

Published

2024

Language

EN