# DEGREE REGULATIONS & PROGRAMMES OF STUDY 2009/2010

 University Homepage DRPS Homepage DRPS Search DRPS Contact

# Logic and Automata (Level 10) (U03647)

? Credit Points : 10  ? SCQF Level : 10  ? Acronym : INF-4-LA-4

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
specify and transform tree-structured documents.

While all computer scientists see finite-state automata over strings, it is other types of automata that are commonly used in applications nowadays: they differ in structures over which they run (strings or trees, finite or infinite), and the mode of running (deterministic,
nondeterministic, alternating).

The course is about these models of automata, their logical
counterparts, and applications of the logic/automata connections in various areas of computer science.

### Entry Requirements

? 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)

### Delivery Information

? Normal year taken : 4th year

? Delivery Period : Not being delivered

? 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.

### Assessment Information

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.

Course Secretary

Miss Kate Weston
Tel : (0131 6)51 5610
Email : kate.weston@ed.ac.uk

Course Organiser

Dr Amos Storkey
Tel : (0131 6)50 4491
Email : A.Storkey@ed.ac.uk

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/

 Navigation Help & Information Home Introduction Glossary Search Regulations Regulations Degree Programmes Introduction Browse DPTs Courses Introduction Humanities and Social Science Science and Engineering Medicine and Veterinary Medicine Other Information Timetab Print on Demand (Only accessible to staff and students of the University of Edinburgh) Prospectuses Important Information
copyright 2009 The University of Edinburgh