Thesis Topic Details

Topic ID:
3484
Title:
On degrees of nondeterminism in finite automata and related concepts
Supervisor:
Kai Engelhardt
Research Area:
Theory, formal languages, automata theory
Associated Staff
Assessor:
Rob van Glabbeek
Topic Details
Status:
Active
Type:
Research
Programs:
CS
Group Suitable:
No
Industrial:
Yes
Pre-requisites:
COMP4141
Description:
NFAs as acceptors of finite words are exponentially more succinct than DFAs but they recognise the same class of languages: the regular languages. The differences between NFAs and DFAs become more pronounced when using them as acceptors of trees, infinite words, or infinite trees. Quite a few problems in those areas are undecidable or infeasible for NFAs but feasible for DFAs. This has lead researchers to investigate restricted notions of non-deterministic finite automata such as unambiguous, strongly unambiguous, prophetic, top-down deterministic, bottom-up deterministic, guidable, "good for games", etc.

The aim of this thesis is to extend the body of knowledge in this area.
Comments:
--
Past Student Reports
 
No Reports Available. Contact the supervisor for more information.

Check out all available reports in the CSE Thesis Report Library.

NOTE: only current CSE students can login to view and select reports to download.