Permutation rewriting and algorithmic verification

We propose a natural subclass of regular languages (Alphabetic Pattern Constraints, APC) which is effectively closed under permutation rewriting, i. e. , under iterative application of rules of the form ab → ba. It is well-known that regular languages do not have this closure property, in general. Our result can be applied for example to regular model checking, for verifying properties of parametrized linear networks of regular processes, and for modeling and verifying properties of asynchronous distributed systems. We also consider the complexity of testing membership in APC and show that the question is complete for PSPACE when the input is an NFA, and complete for NLOGSPACE when it is a DFA. Moreover, we show that both the inclusion problem and the question of closure under permutation rewriting are PSPACE-complete when we restrict to the class APC.

Authors

• Ahmed Bouajjani
• Anca Muscholl
• Tayssir Touili

Keywords

• Regular model checking
• Semi-commutations
• Rewrite systems
• Verification