TL;DR
While regular expressions (regex) are a staple of everyday software engineering, their computational learnability has long remained a theoretical mystery. This paper establishes that learning succinct regular expressions from data is computationally hard under standard cryptographic assumptions, even when given uniform data distributions or the ability to actively query the target system. Crucially, the authors show that these constraints are fundamentally distinct from known hardness results for finite automata due to massive exponential gaps in how efficiently each format describes a language.
What Problem Does This Paper Address?
In machine learning and theoretical computer science, we often want to know if a computer can automatically learn a rule or concept given examples (PAC learning) or by asking questions (Membership Queries). We have known for decades that learning Deterministic Finite Automata (DFAs) is hard. Since DFAs and Regular Expressions (REs) describe the exact same set of languages (regular languages), you might think that regular expressions are automatically hard to learn too.
However, learning complexity is measured relative to the size of the representation. As the authors highlight, translating a regular expression into a DFA (or vice versa) can cause an exponential or even super-exponential explosion in size.
Because a language might have a very short, simple regular expression but a massive, complex DFA, existing DFA hardness proofs don't apply. This paper addresses this long-standing gap: Is it computationally tractable to learn a regular expression in time polynomial to the length of the expression itself?
Methods
To prove that learning regular expressions is hard, the authors use prediction-preserving reductions. They take known computationally hard problems from learning theory and cryptanalysis and show that if you could efficiently learn a regular expression, you could also solve these notoriously hard problems.
Specifically, they deploy three distinct reduction strategies:
- For Distribution-Free PAC Learning: They map polynomial-size Disjunctive Normal Forms (DNFs)—a classic representation of boolean logic—directly into plain regular expressions, carrying over known DNF hardness results.
- For Uniform Distribution PAC Learning: DNF hardness doesn't hold under uniform distributions, so the authors use a framework based on Local Pseudorandom Generators (local PRGs). They construct a clever hyperedge encoding scheme to show that an efficient regex learner could be used to distinguish truly random strings from pseudorandom ones, breaking the PRG.
- For Extended Regular Expressions: When regular expressions are extended with advanced operators like intersection ($\cap$) or complement ($\neg$), the authors reduce the problem from learning polynomial-size Boolean formulas, leveraging cryptographic hardness assumptions established by Kharitonov.
Datasets
Not discussed in the paper. As a purely theoretical computer science paper, the work relies on mathematical proofs and complexity-theoretic reductions rather than empirical datasets or benchmarks.
Key Insights and Ideas
- Representation is Everything: The core takeaway is that learnability depends entirely on the description length (the "prior") induced by the model, not just the underlying concept class. Even though DFAs, NFAs, and REs are mathematically equivalent, their learning landscapes look entirely different.
- The DFA vs. RE Asymmetry: A striking example of this asymmetry appears when the learner is allowed to make membership queries (MQ). Under this condition, DFAs become perfectly learnable in polynomial time (via Angluin’s famous $L^*$ algorithm). Yet, as this paper proves, plain regular expressions remain stubbornly hard to learn.
- Star-Free Hardness: The authors show that the hardness of learning regular expressions under the uniform distribution holds even if you strip away the Kleene star ($*$) operator, meaning that even "star-free" regexes consisting only of unions and concatenations are hard to learn.
Key Results
The paper maps out a comprehensive taxonomy of tractability and hardness across different variations of automata and regular expressions.
The primary new findings include:
- Plain REs (supporting union, concatenation, and Kleene star) are hard to learn in a distribution-free PAC setting under several standard assumptions (local-PRG, random $k$-SAT, sparse LPN).
- Plain REs are hard to PAC-learn even under a uniform distribution, relying on the local-PRG assumption.
- Extended REs (with intersection or complement) are hard to learn even with the benefit of membership queries under a uniform distribution, based on standard cryptographic assumptions like RSA or factoring Blum integers.
Limitations and Future Work
While this paper maps out most of the regex learning landscape, a few intriguing questions remain open:
- The Uniform Distribution + MQ Blindspot: The authors note that it remains unknown whether plain REs or NFAs can be efficiently learned if you combine a uniform distribution with membership queries (indicated by the question marks in Table 1).
- Coarse-Grained Complexity: The current analysis focuses broadly on polynomial-time tractability. The authors suggest that future work could explore a more refined, finer-grained quantitative analysis of exact sample complexity and runtime bounds.
- Reliance on Assumptions: As is standard in computational complexity, these hardness results are conditional on unproven (but widely accepted) cryptographic assumptions (like the hardness of RSA or the existence of local PRGs).
Summary updated