Login
Talks & Seminars
Title: Decomposing circuits: a multidimensional + language-theoretic approach
Dr. Michaël Cadilhac, Tubingen University, Germany
Date & Time: January 7, 2016 10:15
Venue: Conference Room, ‘C’ Block, 01st Floor, Dept. of CSE, Kanwal Rekhi (KReSIT) Bldg
Abstract:
Circuits are naturally decomposed in their successive layers. How is that decomposition expressed in a language-theoretical setting? We propose to address that question, that closely parallels a similar question on the structure of logical formulas specifying languages. More precisely, we devise a product of languages that allows to see classes of languages recognized by circuits as the closure of elementary languages under this product. Working on picture languages rather than word languages, we overcome the usual limitation that only circuits with \emph{linear fan-in} can be specified, and our treatment thus allows arbitrary fan-ins. This offers a solid foundation for a precise and purely language-theoretic correspondence between multiple frameworks, including logic, algebra, circuits, and branching programs. Co-authors: Andreas Krebs, Klaus-Jörn Lange
Speaker Profile:
Dr. Michaël Cadilhac is a postdoctoral fellow in Tubingen University, Germany. Prior to this he was a graduate student in Montreal University, Canada. His thesis work was focused on semilinear constraints in automata. His research interests include {language,automata} theory, {descriptive, computational, circuit} complexity, and the interplay between these subjects and algebra.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback