Pattern languages (PAT) are a class of languages generated by expressions called patterns that may contain variables. In a pattern, each variable can be instantiated with an arbitrary string. Typed pattern languages extend PAT by associating a type (constraint) with each variable that restricts the domain of allowed substitutions. In this paper, we study regular-typed PAT (PATwRT), where all types are represented either by a regular expression or by an ε-NFA. We consider the PATwRT matching problem for patterns with a single repeated variable of the form P = α₁ β α₂ β ⋯ β α_K. We present simple algorithms whose running time is linear in K and quadratic in the input length N, with polynomial dependence on the sizes of the type representations. Our results extend previous quadratic-time work in two directions: (1) the quadratic-time algorithm for untyped PAT of Fernau et al. (STACS 2015), and (2) the quadratic-time algorithm for the restricted PATwRT K = 3, i.e., α₁ β α₂ β α₃ of Nogami and Terauchi (MFCS 2025).

Regular Expression Denial of Service (ReDoS) is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust computational resources of systems. Even quadratic-time behavior in matching engines has been exploited in successful attacks, as exemplified by major outages at Stack Overflow (2016) and Cloudflare (2019). These incidents motivate a fundamental question: Is it possible to construct matching engines that run in linear or near-linear time in the length of the input string? For classical regular expressions (REGEX), Thompson’s construction yields a linear-time algorithm for fixed expressions. However, practical engines support powerful features such as backreferences, which allow capturing a substring and reusing it later. This feature strictly extends the expressive power of REGEX but unfortunately increases the risk of ReDoS attacks. This paper investigates the fine-grained complexity of the string matching problem for regular expressions with backreferences (REWBs). Specifically, we consider r-use k-REWBs, i.e., REWBs with k variables such that, in any computation, the total number of backreference executions is at most r. On the hardness side, we show that the string matching problem for k-REWBs cannot be solved in O(n^{2k-ε}) time for any ε > 0 under the Strong Exponential Time Hypothesis (SETH), where n is the length of the input string. We also prove that this problem is W[2]-hard when parameterized by the length of the REWB expression, strengthening the previous W[1]-hardness result. Moreover, we prove that this problem for 2-use 2-REWBs cannot be solved in n^{1+o(1)} time unless the triangle detection problem can be solved in that time. On the algorithmic side, we present an O(n log² n)-time algorithm for 1-use REWBs. In particular, we focus on the ABCBD problem, which is the REWB matching problem for the form A(B)_xC∖xD where A, B, C, and D are fixed REGEXes. We also show that every 1-use REWB can be transformed into this canonical form. Our algorithm significantly improves upon the recent O(n²)-time algorithm for the ABCBD problem by Nogami and Terauchi (MFCS, 2025). Our algorithm is highly nontrivial and employs several techniques, including suffix trees, transition monoids of REGEXes, factorization forest data structures, and periodicity of strings.

Backreferences and lookaheads are vital features to make classical regular expressions (REGEX) practical. Although these features have been widely used, understanding of the unrestricted combination of them has been limited. Practically, most likely, no implementation fully supports them. Theoretically, while some studies have addressed these features separately, few have dared to combine them. Those few studies showed that the amalgamation of these features significantly enhances the expressiveness of REGEX. However, no acceptable expressivity bound for REWBLk - REGEX with backreferences and lookaheads - has been established. We elucidate this by establishing that REWBLk coincides with NLOG, the class of languages accepted by log-space nondeterministic Turing machines (NTMs). In translating REWBLk to log-space NTMs, negative lookaheads are the most challenging part since it essentially requires complementing log-space NTMs in nondeterministic log-space. To address this problem, we revisit Immerman-Szelepcsényi theorem. In addition, we employ log-space nested-oracles NTMs to naturally handle nested lookaheads of REWBLk. Utilizing such oracle machines, we also present the new result that the membership problem of REWBLk is PSPACE-complete.

Erasure coding (EC) affords data redundancy for large-scale systems. XOR-based EC is an easy-to-implement method for optimizing EC. This paper addresses a significant performance gap between the state-of-the-art XOR-based EC approach (~4.9 GB/s coding throughput) and Intel's high-performance EC library based on another approach (~6.7 GB/s). We propose a novel approach based on our observation that XOR-based EC virtually generates programs of a Domain Specific Language for XORing byte arrays. We formalize such programs as straight-line programs (SLPs) of compiler construction and optimize SLPs using various program optimization techniques. Our optimization flow is three-fold: 1) reducing the number of XORs using grammar compression algorithms; 2) reducing memory accesses using deforestation, a functional program optimization method; and 3) reducing cache misses using the (red-blue) pebble game of program analysis. We provide an experimental library, which outperforms Intel's library with an ~8.92 GB/s throughput.