Tree automata and minikanren

[Kakadu]

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

[William Byrd]

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

--
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 minikanren+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/minikanren/CAGmVoG3zxk0YVssA9kXEAamb6PbWA5xpaUCARemqujkbVKzf%3DQ%40mail.gmail.com.