Solving Language Equations Using Flanked Automata

Abstract

We define a new subclass of nondeterministic finite automata for prefix-closed languages called Flanked Finite Automata (FFA). Our motivation is to provide an efficient way to compute the quotient and inclusion of regular languages without the need to determinize the underlying automata. These operations are the building blocks of several verification algorithms that can be interpreted as language equation solving problems. We provide a construction for computing a FFA accepting the quotient and product of languages that is compositional and that does not incur an exponential blow up in size. This makes flanked au-tomata a good candidate as a formalism for compositional design and verification of systems.

Publication
In ATVA 201614th International Symposium on Automated Technology for Verification and Analysis