A Relational Exploration of the Chomsky Hierarchy

Explore the Chomsky Hierarchy through a relational lens in this 50-minute conference talk from Strange Loop 2013. Delve into the world of miniKanren, a domain-specific language for relational programming, as Daniel Friedman and William Byrd demonstrate how to encode various automata and Turing Machines. Learn how these relational implementations can not only accept strings for given languages but also generate strings and associated data structures. Gain insights into the power of relational programming and the inner workings of automata and Turing Machines through this innovative approach to the Chomsky Hierarchy.

"A Relational Exploration of the Chomsky Hierarchy" by Daniel Friedman and William Byrd (2013)