Decision problems for regular languages

Given a class of regular languages, the C-membership problem asks whether a given regular language belongs to C. While most questions about automata are well understood today, the C-membership problem remains open for several significant classes, in particular for most levels of the quantifier alternation hierarchy in first-order logic. This talk will present approaches to solving this problem, aimed at simultaneously capturing several variants of a specific level.

Authors

• Marc Zeitoun

Keywords

No keywords are indexed for this paper.