Difference between revisions of "Lat18"

From Numerical Transition Systems
Jump to: navigation, search
Line 15: Line 15:
 
'''Level''': PhD and Master 2
 
'''Level''': PhD and Master 2
  
'''Schedule''': Thursdays between 10h00 and 13h00  
+
'''Schedule''': Mondays between 10h00 and 13h00  
  
* Oct 04: [http://www-verimag.imag.fr/~iosif/LAT/w1_mon.pdf Introduction, First and Second Order Logics]
+
* Oct 08: [http://www-verimag.imag.fr/~iosif/LAT/w1_mon.pdf Introduction, First and Second Order Logics]
* Oct 11: [http://www-verimag.imag.fr/~iosif/LAT/w1_tue.pdf Automata on Finite Words]
+
* Oct 15: [http://www-verimag.imag.fr/~iosif/LAT/w1_tue.pdf Automata on Finite Words]
* Oct 18: [http://www-verimag.imag.fr/~iosif/LAT/w1_thu.pdf Automata on Infinite Words]
+
* Oct 22: [http://www-verimag.imag.fr/~iosif/LAT/w1_thu.pdf Automata on Infinite Words]
* Oct 25: [http://www-verimag.imag.fr/~iosif/LAT/w1_sat.pdf Linear Temporal Logic]
+
* Oct 29: [http://www-verimag.imag.fr/~iosif/LAT/w1_sat.pdf Linear Temporal Logic]
* Nov 01: [http://www-verimag.imag.fr/~iosif/LAT/w2_mon.pdf Automata on Finite Trees]
+
* Nov 05: [http://www-verimag.imag.fr/~iosif/LAT/w2_mon.pdf Automata on Finite Trees]
* Nov 08: [http://www-verimag.imag.fr/~iosif/LAT/w2_tue.pdf Automata on Infinite Trees]
+
* Nov 12: [http://www-verimag.imag.fr/~iosif/LAT/w2_tue.pdf Automata on Infinite Trees]
* Nov 29: [http://www-verimag.imag.fr/~iosif/LAT/w2_wed_1.pdf Game Theory Motivation], [http://www-verimag.imag.fr/~iosif/LAT/w2_wed_2.pdf Terminology], [http://www-verimag.imag.fr/~iosif/LAT/w2_wed_3.pdf Reachability and Buchi games]  
+
* Nov 26: [http://www-verimag.imag.fr/~iosif/LAT/w2_wed_1.pdf Game Theory Motivation], [http://www-verimag.imag.fr/~iosif/LAT/w2_wed_2.pdf Terminology], [http://www-verimag.imag.fr/~iosif/LAT/w2_wed_3.pdf Reachability and Buchi games]  
* Dec 6: [http://www-verimag.imag.fr/~iosif/LAT/w2_thu_2.pdf Parity games] [http://www-verimag.imag.fr/~iosif/LAT/w2_fri_1.pdf Games and Tree Automata]
+
* Dec 3: [http://www-verimag.imag.fr/~iosif/LAT/w2_thu_2.pdf Parity games] [http://www-verimag.imag.fr/~iosif/LAT/w2_fri_1.pdf Games and Tree Automata]
  
 
'''Location''': [https://batiment.imag.fr/ IMAG building], Room: TBA
 
'''Location''': [https://batiment.imag.fr/ IMAG building], Room: TBA

Revision as of 19:57, 26 September 2018

Logic and Automata Theory

Lecturer: Radu_Iosif

Objectives: Many major hardware (Intel, IBM) and software (Microsoft) companies are now using the technique of Model Checking in practice. Examples of its use include the verification of VLSI circuits, communication protocols, software device drivers, real-time embedded systems, and security algorithms. The works of A. Pnueli, E. Clarke, E.A Emerson and J. Sifakis on algorithmic verification of systems using the Model Checking has been awarded the 1996 and 2007 Turing awards. The basis of this work is the relation of logic with automata theory, which was introduced by the seminal works of Buechi (1960) and Rabin (1969). This course is intended to introduce the student to these techniques, focusing on decision methods for classical non-interpreted logics and integer arithmetic theories.

Syllabus:

  • Classical first- and second-order logic, finite word and tree automata, closure properties and language emptiness.
  • Relationship between Weak Monadic Second-Order Logic and finite automata.
  • Infinite automata on words (Buechi, Mueller) and on trees (Rabin) automata, and their relationship with Monadic Second-Order Logic.
  • Game theory. Proof of Rabin's Complementation Theorem. Application of game theory to logic.

Prerequisites: basic notions of boolean logic

Level: PhD and Master 2

Schedule: Mondays between 10h00 and 13h00

Location: IMAG building, Room: TBA

Register:

  • send email to Radu.Iosif@univ-grenoble-alpes.fr indicating your name and year of Phd/Master program
  • for PhD students, indicate also your host laboratory and name of your PhD advisor

Past LAT courses