Title: Cover Languages — Main Results and Applications
Abstract: The concept of Deterministic Finite Cover Automata (DFCA) was first introduced in 1998 at WIA ’98. Several minimization algorithms have been developed for this type of automata recognizing finite languages. The idea was then extended to include the non-deterministic versions of cover automata. The latest extension includes deterministic automata with do-not-care symbols and multiple entries. It has been proven that most problems related to non-deterministic versions of cover automata are NP-hard. In this talk, we present a survey of results and some recent applications of cover automata.
The talk will take place physically at FMI Hall 214 “Google”.