Combinatory Logic synthesis and alternation

We discuss complexity theoretic results in the context of Combinatory Logic Synthesis which is a new approach to component-based synthesis using type inhabitation. The complexity theoretic reductions behind these results establish explicit and effective connections between combinatory logic inhabitation and automata theoretic models, in the form of alternating tree automata and alternating space bounded Turing machines. These computational models that are commonly found in automata theoretic approaches are related to synthesis based on logics within the MSO family of logics.

Authors

• Boris Düdder
• Moritz Martens
• Jakob Rehof:

Keywords

No keywords are indexed for this paper.