Sixteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2001)

Paper: Permutation Rewriting and Algorithmic Verification (at LICS 2001)

Authors: Ahmed Bouajjani Anca Muscholl Tayssir Touili


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 \rightarrow 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.


    author = 	 {Ahmed Bouajjani and Anca Muscholl and Tayssir Touili},
    title = 	 {Permutation Rewriting and Algorithmic Verification},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {399--},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}