THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2013/2014
Archive for reference only
THIS PAGE IS OUT OF DATE

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Postgraduate Course: Logic and Automata (Level 11) (INFR11051)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Course typeStandard AvailabilityNot available to visiting students
Credit level (Normal year taken)SCQF Level 11 (Postgraduate) Credits10
Home subject areaInformatics Other subject areaNone
Course website http://www.inf.ed.ac.uk/teaching/courses/la/ Taught in Gaelic?No
Course descriptionAutomata 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 (not applicable to Visiting Students)
Pre-requisites Co-requisites
Prohibited Combinations Students MUST NOT also be taking Logic and Automata (Level 10) (INFR10030)
Other requirements For Informatics PG and final year MInf students only, or by special permission of the School. Informatics 2D is strongly recommended.

Students should understand the following topics:

Computation: the definition as acceptor and transducer, deterministic/non deterministic machines, regular expressions, operations on FSMs

Propositional and predicate logic

Context-free languages and Push-down automata

Turing machines and computability
Additional Costs None
Course Delivery Information
Not being delivered
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