THE UNIVERSITY of EDINBURGH
DEGREE REGULATIONS & PROGRAMMES OF STUDY 2009/2010
Logic and Automata (Level 10) (U03647)
Automata are a natural procedural counterpart of declarative, or logical formalisms that appear in various areas of computer science. The most visible applications of the logic/automata connections are in the areas of formal verification, XML, and decidability of logical theories. In verification, automata are used to reason about infinite computations; in XML, they are used to
? Pre-requisites : Informatics 1A Informatics 2A Successful completion of Year 3 of an Informatics Single or Combined Honours Degree, or equivalent by permission of the School. Informatics 2D is strongly recommended.
? Prohibited combinations : Logic and Automata (Level 11)
? Normal year taken : 4th year
? Contact Teaching Time : 2 hour(s) per week for 10 weeks
Summary of Intended Learning Outcomes
1 - Students will be able to identify different models of
automata, in particular, automata on finite trees, infinite strings, infinite trees, as well as different running modes of automata: deterministic, nondeterministic, alternating.
2 - Students will be able to translate logical specifications into automata;
3 - Students will know how to solve decision problems for
different types of automata and their complexity.
4 - Students will know how to use logical formalisms and automata in specifying software and hardware properties, and how to use automata decision problems for solving verification problems.
5 - Students will know how logical and automata formalisms
influence the design of XML schemas and query languages.
6 - Students will learn how automata provide algorithms for
deciding logical theories, and how these decision procedures are used in practice.
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Three sets of exercises, worth 5% each.
Two assignments, worth 30% each.
Contact and Further Information
The Course Secretary should be the first point of contact for all enquiries.
Miss Kate Weston
Dr Amos Storkey
Course Website : http://www.inf.ed.ac.uk/teaching/courses/
School Website : http://www.informatics.ed.ac.uk/
College Website : http://www.scieng.ed.ac.uk/