Search

• < Previous
• 1
• Next >

---

A Functional (Monadic) Second-Order Theory of Infinite Trees

Anupam Das ; Colin Riba.

This paper presents a complete axiomatization of Monadic Second-Order Logic (MSO) over infinite trees. MSO on infinite trees is a rich system, and its decidability ("Rabin's Tree Theorem") is one of the most powerful known results concerning the decidability of logics. By a complete axiomatization&nbsp;[&hellip;]

---

A Curry-Howard Approach to Church's Synthesis

Pierre Pradic ; Colin Riba.

Church's synthesis problem asks whether there exists a finite-state stream transducer satisfying a given input-output specification. For specifications written in Monadic Second-Order Logic (MSO) over infinite words, Church's synthesis can theoretically be solved algorithmically using automata and&nbsp;[&hellip;]

---