the permutation defined by the set $\{p_1,\dots,p_n\}$ of points. It can be seen that ${\varphi}$ does not depend on the particular choice of $d_1,\dots,d_n$, and thus ${\varphi}{\::\:}\Sigma^\ast\to {\operatorname{Geom}}(M)$ is a well-defined mapping.

The mapping ${\varphi}$ is many-to-one, and so for enumerative applications we must restrict its domain to a set $L\subseteq\Sigma^\ast$ on which ${\varphi}$ is injective. We seek to choose $L$ to be a *regular language*. The regular languages are those that can be obtained from the empty language and the singleton languages using the operations of union, concatenation, and Kleene star (where $K^*$ is the set of all concatenations of 0 or more words from $K$). Alternatively, regular languages can also be characterised as those accepted by deterministic finite state automata. From this latter viewpoint it follows (e.g., by the transfer matrix method) that regular languages have rational generating functions (either when enumerated by length, or with a separate variable $x_a$ for each $a \in \Sigma$). We refer readers to [@flajolet:analytic-combin: Section I.4 and Appendix A.7] for more information on regular languages.

The following theorem from [@albert:geometric-grid-:] demonstrates the connection between subclasses of geometric grid classes and regular languages. Essentially, it says that all such classes are extremely well 