Revisiting finite automata and their relation with languages and circuits

Title: Revisiting finite automata and their relation with languages and circuits
Speaker: Prof. Gérard Berry (Collège de France, France)
Time: 15:00, Thursday, December 13th, 2012
Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
Abstract:
The theory and practice of finite automata (also called finite state machines of FSMs in the circuit design area) is generally thought to be well-understood and more or less finished. We show that this view is overly simplistic, and discuss a new approach born with the development of the Esterel synchronous programming language. The development and implementation of Esterel has led us to revisit many of the classical views about the relation between languages and automata, the role of deterministic vs. non-deterministic automata, the efficient implementation of automata in software or hardware, and the formal verification of their properties. In particular, we show that the most widely used techniques to implement automata by synchronous circuits are neither optimal nor efficient, and that better designed language based on appropriate concurrency and hierarchy primitives yield better specification, implementation, and formal verification capabilities.

Bio:

Gérard Berry is professor at Collège de France, where he holds the chair “Algorithms, Languages, and Machines”. His interest are mathematical models of computation, programming language and semantics, reactive and real-time systems, circuit design, synthesis, and formal verification, and the diffusion of Informatics to a wide audience. He started his career in the 1970’s at Ecole des mines de Paris and Inria, working on the definition and semantics of mathematical calculi and programming languages. In 1977, he moved to Sophia-Antipolis (French Riviera), where he participated in the creation of the Center of Applied Mathematics of Ecole des Mines and later of the local Inria center. In 1983, he defined the Esterel programming language dedicated to reactive and real-time systems, and extended this language to hardware synthesis in 1989. The early versions of Esterel were industrialized by ILOG and used in avionics, telecommunications, etc.. In the 1990’s, Gérard Berry consulted with Digital Equipment, Cadence Design Systems, Synopsys, and Intel, which led him to define a much more elaborate Esterel v7 language dedicated to both hardware synthesis and software real-time systems applications. In 2001, Gérard Berry moved to industry and became Chief Scientist of the newly created Esterel Technologies company, directing the development of Esterel v7 and taking part in the design of the flagship SCADE 6 language dedicated to safety-critical embedded applications in avionics, railways, automotive, etc. In 2009, he left Esterel Technologies to become Director of Research at Inria and president of the Inria Evaluation Committee. He became full professor at Collège de France in September 2012, after having held two yearly chairs there: the Innovation Technology chair in 2007-2008 (course “How and Why the World Becomes Digital”) and the “Informatics and Digital Sciences” Chair in 2009-2010 (course “Thinking About, Modeling and Mastering Computation”).

 

Gérard Berry is member of the French Académy of Sciences and Academy of Technologies, and member of Academia Europaea. He received the Monpetit Award of Académie des Sciences, the Bronze Medal of CNRS, the Science and Defense Award, and the EADS Great Prize for the applications of sciences to industry.