5 ms·
In computer science academia, this kind of game is called grammar induction (of which inferring regular expressions is a special case). A classic algorithm for
by long 9y ago
In computer science academia, this kind of game is called grammar induction (of which inferring regular expressions is a special case).
A classic algorithm for inferring regular expressions was given by Angluin: https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/papers/angluin87.pdf https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape...
(This isn't quite the same setup as you're thinking of but there are a ton of variations on the basic idea)
- eru 9y agoThanks. I had figured out that grammar induction was the right word to look for a while ago. (But took me a bit to find it.) I know the paper you linked to, but yes, it's not quite the right setup.
- long 9y agoThere's a conference on grammar induction called ICGI; might wanna browse through the proceedings to see if there's anything closer.
- eru 9y agoThanks! I'm basically interested in the equivalent of the "guessing game" for regular expressions. (See eg https://stackoverflow.com/questions/5440688/the-guess-the-number-game-for-arbitrary-rational-numbers https://stackoverflow.com/questions/5440688/the-guess-the-nu... for a rational number solution.) With a fixed guesser, that would encode all regular expressions / finite automata as sequences of binary digits. (But in a interestingly different way from just serializing the table for a DFA, or writing down the regular expression in ASCII characters.)
- long 9y agoSo I do AI research on something pretty related to the guessing game -- I'll shoot you an email.