Derivatives and partial derivatives for regular shuffle expressions

摘要

There is a rich variety of shuffling operations ranging from asynchronous interleaving to various forms of synchronizations. We introduce a general shuffling operation which subsumes earlier forms of shuffling. We further extend the notion of a Brzozowski derivative and an Antimirov partial derivative to the general shuffling operation and thus to many earlier forms of shuffling. This extension enables the direct construction of automata from regular expressions involving shuffles that appear in specifications of concurrent systems. (C) 2016 Elsevier Inc. All rights reserved.