We define the notion of location for regular expressions with shuffle by extending the notion of position in standard regular expressions. Locations allow for the definition of the sets Follow, First, and Last with their usual semantics. From these, we construct an automaton for regular expressions with shuffle (APOS), which generalises the standard position/Glushkov automaton. The sets mentioned above are also the foundation for other constructions, such as the Follow automaton, and automata based on pointed expressions. As a consequence, all these constructions can be generalised to the shuffle operator. We show that the partial derivative automaton is a right-quotient of APOS. We relate APOS with another automaton construction based on positions that has been previously studied (A∂pos). The prefix automaton is extended to the shuffle operator and shown not to be a quotient of APOS. Locations are also used to define a position automaton for regular expressions with the intersection.

Several notions of synchronisation in concurrent systems can be modelled by regular shuffle operators. In this paper we consider regular expressions extended with three operators corresponding respectively to strong, arbitrary, and weak synchronisation. For these expressions, we define a location based position automaton. Furthermore, we show that the partial derivative automaton is still a quotient of the position automaton.

2D regular expressions represent rational relations over two alphabets Σ and Δ. In standard 2D expressions (S2D-RE) the basic terms are generators of Σ⋆×Δ⋆, while in generalised 2D expressions (2D-RE) the basic terms are pairs of (ordinary) regular expressions over one alphabet (1D). In this paper we study the average state complexity of partial derivative standard transducers (TPD) for both S2D-RE and 2D-RE. For S2D-RE we obtain the same asymptotic bounds as for partial derivative automata. For 2D-RE, while in the worst case the number of states of TPD can be O(n2), where n is the size of the expression, asymptotically and on average that value is bounded from above by O(n32). We also show that asymptotically and on average the alphabetic size of a 2D-RE is half of its size. All results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. In particular, we generalise the methods developed in previous work to a broad class of analytic functions.