Alladi Ramakrishnan Hall

Recognizing languages: A unified approach of circuits, logic, and algebra

Michael Cadilhac

Univ of Tuebingen

Circuits, logical formulas, and monoids share a similar structuralinductive flavor: they can be incrementally built from small building blocks. The precise correspondence between these constructions is investigated, and put under a uniform language-theoretic framework. This provides a systematic method to study well-behaved classes of languages through the prisms of circuit complexity, logic, and algebra.


Work in progress with Andreas Krebs and Klaus-Joern Lange.