Regular languages, property satisfiability, and shortcuts

Abstract

The Language Server (LaSer ) is a website created to ask and answer various questions pertaining to regular languages. One of its main features is testing property satisfiability, that is, does a given regular language satisfy a particular property. If a regular language does satisfy the property, we can then ask if the language is maximal with respect to the property. That is, L is maximal if it is not properly contained in any language satisfying the property. Deciding if a language is maximal reduces to deciding if a language is universal, which is known to be PSPACE-complete. However, for some practical purposes, we need only know if a language is approximately maximal. That is p%-maximal. Using a randomized algorithm, we can check if a language is as maximal as we want, by repeatedly adding words and testing whether the language still satisfies the property. This new property is called pseudo-maximality, and is much easier to test.