Adding Modular Predicates

The decision problem for a given class of regular languages consists in deciding, given a regular language, whether or not it belongs to this class. Solving the decision problem for various fragments of monadic second order is a well-studied problem on regular languages. Fragments of logic are usually defined in terms of their quantifier complexity (Σ n -classes) or number of variables allowed in the formulae. Another possible parameter is to impose restrictions on the numerical predicates in the signature. There are essentially three basic groups of such predicates: the linear order, the local predicates LOC and the modular predicates MOD. In this talk, we will presents generic algorithmic procedure for the enrichement of a fragment by modular predicates, depending on algebraic assumptions on the initial fragment.

Authors

• Charles Paperman

Keywords

No keywords are indexed for this paper.