Hi Dmitrii! About 7 years ago Michael Adams, Michael Ballantyne, and I tried to explore tree automata for miniKanren, inspired by goals similar to yours! Michael Adams implemented a tree automata solver:
https://github.com/webyrd/tree-automata We had trouble, though, figuring out how to integrate the tree automata solver with the rest of miniKanren. Also, I couldn't figure out how =/= and absento work in the presence of tree automata. I suspect there is a way to integrate tree automata and disequality constraints with miniKanren. We didn't spend much time on the integration. I've wanted to revisit this area of research for many years. I do think tree automata are promising, and I hope you will explore this area! :) Cheers, --Will On Tue, Mar 22, 2022 at 9:28 AM Kakadu <[email protected]> wrote: > Hello! > > I'm wondering have anybody tried to use miniKanren with tree automata? > For example, add constraints based on tree automata, or, even crazier, > replace the language of tree-like terms by a language of tree > automata? > > Existence of this stuff may help us to represent some predicated > finitely, for example, all odd Peano numbers have finite > representation as tree automaton, but right now in miniKanren they are > an infinite stream of examples. > > I think that it should be doable in theory because tree automata are > not as powerful as arbitrary relations, for example, it is not > obvious how to check with tree automata that two lists has the same > length, because you can't count how many times you walked through > transitions. In principle, you could multiple two automata and get a > synchronous tree automaton, but it is a different beast... > > Happy hacking, > Dmitrii > > -- > You received this message because you are subscribed to the Google Groups > "minikanren" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/minikanren/CAGmVoG3zxk0YVssA9kXEAamb6PbWA5xpaUCARemqujkbVKzf%3DQ%40mail.gmail.com > . > -- You received this message because you are subscribed to the Google Groups "minikanren" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/minikanren/CACJoNKHd41tMtPq4h_7OZ-cw7nzWiVsS6Q%3DDLxzperra2p08Wg%40mail.gmail.com.
