Regular Expressions which query an Oracle

At what point do we drop the term &quot;regular&quot; expressions altogether for stuff like this? This is going to sound pedantic since I know that most popularly-used regex implementations are themselves non-regular, but I feel like we&#x27;re just piling more and more stuff on top of good-old-regexes and trying to turn the concept into a catch-all for anything that does pattern matching on text.<p>I guess it just feels icky that &quot;regular expressions&quot; has inherent meaning (i.e. can be represented entirely by a finite automaton) which has become completely diluted at this point.<p>That rant aside, cool paper. The idea of bridging formal language theory with modern computational tooling feels timely. I think I would&#x27;ve liked to see more exploration of oracle-based costs, for instance:<p>* What happens when oracle outputs are inconsistent&#x2F;uncertain?<p>* What happens as oracle interactions become more computationally expensive?

To me this feels kind of similar to the idea of verifying tokens in a compiler by querying an oracle. i.e. in the script compiler for my game engine, there&#x27;s an additional pass at the end of compilation that checks things like filename literals or entity ID literals against a database of assets or a list of all the scripts that were compiled, so when I hit F5 in visual studio any typos in those literals are caught before I waste time booting the game up.<p>It would be interesting to be able to do this eagerly during parsing, so it&#x27;s neat to see people thinking about doing this at a regex level, though I&#x27;m having trouble thinking of specific cases where I would both want to use a regex and want to query an oracle from inside of it...

They said they want the cost of invoking the oracle, the DB, to be low. Might be a good use for in-memory, embedded DB’s with a good API.

There aren’t many papers on the subject, and I’m probably not great at spotting them. The linked paper also doesn’t mention much recent research, so it seems like an excellent opportunity to ask for the collective wisdom of the HN community - what are your favorite undervalued information retrieval papers after 2015?

This article lets an UTF8 symbol be something... so now we have all the existing math symbols + all UTF8 icons. Wonder what the papers be look like in 20 years.