# Finite Automata for Efficient Graph Recognition

Frank Drewes ID Umeå universitet
SE-90187 Umeå
Sweden<EMAIL_ADDRESS>Universität Bremen
D-28334 Bremen
GermanyUniversität der Bundeswehr München
D-85577 Neubiberg
Germany Berthold Hoffmann ID Universität Bremen
D-28334 Bremen
Germany<EMAIL_ADDRESS>Universität der Bundeswehr München
D-85577 Neubiberg
Germany Mark Minas ID Universität der Bundeswehr München
D-85577 Neubiberg
Germany<EMAIL_ADDRESS>
###### Abstract

Engelfriet and Vereijken have shown that linear graph grammars based on
hyperedge replacement generate graph languages that can be considered as
interpretations of regular string languages over typed symbols. In this paper
we show that finite automata can be lifted from strings to graphs within the
same framework. For the efficient recognition of graphs with these automata,
we make them deterministic by a modified powerset construction, and state
sufficient conditions under which deterministic finite graph automata
recognize graphs without the need to use backtracking.

##  1 Introduction

Engelfriet and Vereijken [18] have shown that linear graph grammars based on
hyperedge replacement can be considered as interpretations of linear string
grammars: typed (“doubly ranked”) symbols of an alphabet are interpreted as
basic graphs that have front and rear interfaces of nodes, and string
concatenation is interpreted as the composition of two graphs by gluing the
rear of the first to the front of the second graph. Graph languages
constructed in this way are of bounded pathwidth, and are thus potentially
more efficiently recognizable than general hyperedge replacement languages,
which are known to be NP-complete. However, without additional restrictions
even these graph languages are NP-complete [2].

In this paper we study how finite automata over graph symbols can be
interpreted to recognize graph languages efficiently. Given a graph as input,
the transitions of such an automaton consume the graph step by step while
changing the state of the automaton, in the end reaching either an accepting
or a rejecting state. If the automaton used is nondeterministic, a naive
decision procedure for determining whether the input graph is accepted would
have to use backtracking. While we show in this paper that the transition
relation can be made deterministic by a modified powerset construction,
backtracking may still be needed. This is due to the fact that, whereas a
string starts with a unique first symbol to be read by the first transition of
the computation of a deterministic finite automaton, in general several
alternative basic graphs represented by that symbol may be spelled off at the
front of a graph. We provide two sufficient criteria under which automata can
choose between them without the need to backtrack. These criteria resemble
similar criteria known from efficient parsing algorithms for context-free
hyperedge replacement languages [14, 15].

Work on efficient parsing algorithms for grammars started in the late 1980s,
initiated by the realization that, in general, the graph languages generated
by these grammars can be NP-complete [2, 29]. Early polynomial algorithms were
based on restrictions which either ensure efficiency of the well-known Cocke-
Younger-Kasami algorithm (adapted to hyperedge replacement grammars) or make
sure that the derivation trees of generated graphs mirror a unique recursive
decomposition of graphs into smaller and smaller subgraphs, see [30, 32, 11].
Later work on parsing hyperedge replacement languages include [9, 22] as well
as the authors’ own work on top-down and bottom-up parsers for these
languages; see, e.g., [12, 13, 26, 15, 16]. For a more extensive overview of
work on efficient parsing for graph grammars, including other types of
grammars than those based on hyperedge replacement, see [15, Section 10].

For the efficient recognition of graph languages, finite automata have not
attained the importance that they have for string languages. Some early work
exists on finite automata for algebraic structures [3, 23], rooted directed
acyclic graphs [33], and infinite directed acyclic graphs [28]. Brandenburg
and Skodinis have devised finite automata for linear node replacement grammars
[7]. Bozapalidis and Kalampakas have studied automata on the hypergraphs of
Engelfriet and Vereijken [18] in an algebraic setting [6, 27]. And, Brugging,
König _et al._ have recast these hypergraphs as cospans [4], and have shown
that finite automata defining hypergraph languages are equivalent to
Courcelle’s recognizable hypergraph languages [10]; later these results have
been generalized to hereditary pushout categories [8]. All this work has
focussed on _defining_ the graph languages accepted by finite automata (e.g.,
by composing the graphs labeling the edges passed on a walk through the
transition diagrams of the automata), rather then on _recognizing_ graph
languages in the sense of efficiently deciding their membership problem. In
particular, the efficiency of the recognition process has not been a matter of
concern. In this paper, we focus on this aspect, which is of interest because
the analysis of graphs by finite automata corresponds intuitively to a lexical
analysis in the traditional string-based setting.

The technical contributions of this paper revolve mainly around different
aspects of coping with nondeterminism, which differs in subtle ways from the
string case. Given a nondeterministic automaton over graph symbols, we first
apply a powerset construction to it (Section 4.1). Interestingly, this
construction does not always result in a deterministic automaton. We show,
however, that the resulting automaton is indeed deterministic if the
construction starts from an unambiguous automaton, a condition that can always
be fulfilled (Section 4.2). Next, as mentioned above, even a deterministic
automaton is only deterministic at the string level. As the edges of a graph
do not come in a predefined processing order, recognition still requires
backtracking in general: anytime in the process, several different transitions
may be applicable, and a given transition may have several alternative edges
it may consume. We deal with these problems in Sections 4.3 and 4.4, resulting
in linear-time recognition without backtracking.

The remainder of this paper is structured as follows. We define graphs with
front and rear interfaces and their composition in Section 2. In Section 3, we
introduce finite automata over graph symbols and define how they can be used
to recognize graph languages. Section 4 contains the main technical
contributions, as described above. In Section 5, we conclude the paper and
indicate directions of future research.

##  2 Graphs and Graph Composition

We let $\mathbb{N}$ denote the set of non-negative integers, and $[n]$ the set
$\\{1,\dots,n\\}$ for all $n\in\mathbb{N}$. $A^{*}$ denotes the set of all
finite sequences over a set $A$; the empty sequence is denoted by
$\varepsilon$, $A^{\ast}\setminus\\{\varepsilon\\}$ by $A^{+}$, and the length
of a sequence $\alpha$ by $|\alpha|$. For a sequence $s=a_{1}\cdots a_{n}$
with $n\in\mathbb{N}$ and $a_{1},\dots,a_{n}\in A$, we let
$[s]=\\{a_{1},\ldots,a_{n}\\}$ and $s(i)=a_{i}$ for all $n\in\mathbb{N}$. For
$f\colon A\to B^{*}$, we let $f(a,i)=f(a)(i)$ if $a\in A$ and $i\in[|f(a)|]$.
We silently extend functions to sequences and let $f(a_{1}\cdots
a_{n})=f(a_{1})\cdots f(a_{n})$, for all $n\in\mathbb{N}$,
$a_{1},\dots,a_{n}\in A$, and all functions $f\colon A\to B$. As usual, given
a binary relation $R\subseteq A\times B$, we denote the transitive closure by
$R^{+}$ and the transitive reflexive closure by ${R^{*}}$. Further,
$\mathit{dom}(R)$ denotes the domain of $R$, i.e., $\mathit{dom}(R)=\\{a\in
A\mid\exists b\in B\colon(a,b)\in R\\}$. Finally, we let $R(a)=\\{b\in
B\mid(a,b)\in R\\}$ for every $a\in A$.

We consider edge-labeled hypergraphs (which we simply call graphs). Like Habel
in [24], we supply them with a front and a rear interface, each being a
sequence of nodes.111Other than in [24], however, we do not divide the
attached nodes of edges into sources and targets.

For the labeling of edges, we consider a ranked alphabet
$(\Sigma,\mathit{rank})$ consisting of a set of symbols and a function
$\mathit{rank}\colon\Sigma\to\mathbb{N}$ which assigns a rank to each symbol
$a\in\Sigma$. The pair $(\Sigma,\mathit{rank})$ is usually identified with
$\Sigma$, keeping $\mathit{rank}$ implicit.

######  Definition 2.1 (Graph).

A _graph_ (over $\Sigma$) is a tuple
$G=(\dot{G},\bar{G},\mathit{att}_{G},\allowbreak\mathit{lab}_{G},\allowbreak\mathit{front}_{G},\allowbreak\mathit{rear}_{G})$,
where $\dot{G}$ and $\bar{G}$ are disjoint finite sets of _nodes_ and _edges_
, respectively, the function $\mathit{att}_{G}\colon\bar{G}\to\dot{G}^{*}$
attaches repetition-free sequences of nodes to edges, the function
$\mathit{lab}_{G}\colon G\to\Sigma$ labels edges with symbols in such a way
that $|\mathit{att}_{G}(e)|=\mathit{rank}(\mathit{lab}_{G}(e))$ for every edge
$e\in\bar{G}$, and the repetition-free node sequences
$\mathit{front}_{G},\mathit{rear}_{G}\in\dot{G}^{*}$ specify the _front_ and
_rear_ interface nodes.

The lengths of front and rear interfaces classify graphs as follows: A graph
$G$ _has type $(i,j)$_ if $|\mathit{front}_{G}|=i$ and
$|\mathit{rear}_{G}|=j$; we then write $\mathit{type}(G)=(i,j)$.
$\mathbb{G}_{\Sigma}^{(i,j)}$ denotes the set of all graphs of type $(i,j)$,
and
$\mathbb{G}_{\Sigma}=\bigcup_{i,j\in\mathbb{N}}\mathbb{G}_{\Sigma}^{(i,j)}$
denotes the set of all graphs over $\Sigma$, regardless of type.

For graphs $G$ and $H$, a _morphism_ $m\colon G\to H$ is a pair
$m=(\dot{m},\bar{m})$ of functions $\dot{m}\colon\dot{G}\to\dot{H}$ and
$\bar{m}\colon\bar{G}\to\bar{H}$ that preserve attachments and labels, i.e.,
$\mathit{att}_{H}(\bar{m}(e))=\dot{m}(\mathit{att}_{G}(e))$ and
$\mathit{lab}_{H}(\bar{m}(e))=\mathit{lab}_{G}(e)$ for all $e\in\bar{G}$.
(Note that fronts and rears need not be preserved.) The morphism $m$ is
_injective_ or _surjective_ if both $\dot{m}$ and $\bar{m}$ have this
property, and a _subgraph inclusion_ of $G$ in $H$ if $m(x)=x$ for every node
and edge $x$ in $G$; then we write $G\subseteq H$. $G$ and $H$ are
_isomorphic_ , $G\cong H$, if there exists a surjective and injective morphism
$m\colon G\to H$ such that $\mathit{front}_{H}=m(\mathit{front}_{G})$ and
$\mathit{rear}_{H}=m(\mathit{rear}_{G})$.

Consider $a\in\Sigma$, $n\in\mathbb{N}$, and repetition-free sequences
$\varphi,\varrho\in[n]^{\ast}$ such that $[\varphi]\cup[\mathit{rank}(a)]=[n]$
(where $[\varphi]$ and $[\mathit{rank}(a)]$ are not necessarily disjoint).
Then $\langle a\rangle^{\varphi}_{\varrho}$ denotes the graph $A$ with
$\dot{A}=[n]$, $\bar{A}=\\{e\\}$, $\mathit{lab}_{A}(e)=a$,
$\mathit{att}_{A}(e)=1\cdots\mathit{rank}(a)$, $\mathit{front}_{A}=\varphi$,
and $\mathit{rear}_{A}=\varrho$, whereas
$\langle\varepsilon\rangle^{(n)}_{\varrho}$ denotes the discrete graph $B$
with $\bar{B}=\varnothing$, $\dot{B}=[n]$, $\mathit{front}_{B}=1\cdots n$, and
$\mathit{rear}_{A}=\varrho$. We call $\langle a\rangle^{\varphi}_{\varrho}$ an
_atom_ and $\langle\varepsilon\rangle^{(n)}_{\varrho}$ a _blank_.

Note that $\langle\varepsilon\rangle^{(0)}_{\varepsilon}$ is the empty graph.
Further note that no atom has any node that neither is a front node, nor is it
attached to its only edge. In particular, every rear node is also a front node
or attached to the unique edge of the atom, or both. Moreover, all nodes of a
blank occur in its front interface. Finally recall that our objective is
efficient recognition of graphs, which tries to compose an input graph from a
sequence of atoms and a blank. The requirements on front and rear interfaces
differ because recognition will process graphs from front to rear.

$w$$x$$y$$z$$a$$b$$a$
---
“Star” graph

$1$$2$$b$
---
$\langle b\rangle^{1}_{12}$

$1$$2$$3$$a$
---
$\langle a\rangle^{13}_{123}$

$1$$2$$3$$4$$a$
---
$\langle a\rangle^{134}_{1234}$

$1$$2$$3$$4$$a$
---
$\langle a\rangle^{134}_{234}$

$1$$2$$3$$4$
---
$\langle\varepsilon\rangle^{(4)}_{4}$

Figure 1: A “star” graph, four atoms, and a blank.

######  Example 2.1.

Figure 1 shows a “star” graph, atoms $\langle b\rangle^{1}_{12}$, $\langle
a\rangle^{13}_{123}$, $\langle a\rangle^{134}_{1234}$, and $\langle
a\rangle^{134}_{234}$ using the symbols $a$ and $b$, both of rank $2$, and the
blank $\langle\varepsilon\rangle^{(4)}_{4}$. As usual, we represent nodes by
circles and binary edges by arrows. Front interface nodes are connected with
double lines to the left border of the graph, rear interface nodes with double
lines to its right border. Front and rear nodes are ordered from top to
bottom; the “star” graph, e.g., has the front interface $w$ and the rear
interface $y$.

We follow Engelfriet and Vereijken [18] in defining the composition of graphs
in a way resembling string concatenation.

######  Definition 2.2 (Graph Composition).

Let $G\in\mathbb{G}_{\Sigma}^{(i,k)}$ and $H\in\mathbb{G}_{\Sigma}^{(k,j)}$.
We assume for simplicity that $\mathit{rear}_{G}=\mathit{front}_{H}$,
$\dot{G}\cap\dot{H}=[\mathit{rear}_{G}]=[\mathit{front}_{H}]$, and
$\bar{G}\cap\bar{H}=\varnothing$ (otherwise an appropriate isomorphic copy of
$G$ or $H$ is used). The (_typed_) _composition_ $G\mathop{\odot}H$ of $G$ and
$H$ is the graph $C$ such that $\dot{C}=\dot{G}\cup\dot{H}$,
$\bar{C}=\bar{G}\cup\bar{H}$,
$\mathit{att}_{C}=\mathit{att}_{G}\cup\mathit{att}_{H}$,
$\mathit{lab}_{C}=\mathit{lab}_{G}\cup\mathit{lab}_{H}$,
$\mathit{front}_{C}=\mathit{front}_{G}$, and
$\mathit{rear}_{C}=\mathit{rear}_{H}$. Thus $C\in\mathbb{G}_{\Sigma}^{(i,j)}$.

Note that the composition $G\mathop{\odot}H$ is defined on concrete graphs if
the assumptions in Definition 2.2 are satisfied, but is only defined up to
isomorphism if an isomorphic copy of $G$ or $H$ needs to be taken. To avoid
unnecessary technicalities, we shall assume that these assumptions are indeed
satisfied whenever convenient.

Graphs can be constructed from a finite set of basic graphs using composition
and disjoint union [19, 5] (where the latter concatenates the fronts and rears
of the two graphs involved). If we just use composition, we need finitely many
basic graphs per pair of front and rear interfaces. Instead of the simpler
“atomic graphs” proposed in [18] and by Blume et al. in [4], we use atoms and
blanks here.

######  Lemma 2.3.

Every graph $G$ whose isolated nodes all occur in its front interface is of
the form $A_{1}\mathop{\odot}\cdots\mathop{\odot}A_{n}\mathop{\odot}B$ where
$n=|\bar{G}|$, $A_{1},\dots,A_{n}$ are atoms, and $B$ is a blank.

###### Proof.

Let $G\in\mathbb{G}_{\Sigma}$ with $|\bar{G}|=n$ such that every isolated node
of $G$ occurs in $[\mathit{front}_{G}]$. We prove by induction on $n$ that
there are atoms $A_{1},\ldots,A_{n}$ and a blank $B$ such that $G\cong
A_{1}\mathop{\odot}\cdots\mathop{\odot}A_{n}\mathop{\odot}B$. If $n=0$, all
nodes of $G$ are isolated, and hence $\dot{G}=[\mathit{front}_{G}]$. Then
$G\cong\langle\varepsilon\rangle^{(m)}_{\varrho}$ where $m=|\dot{G}|$ and
$\varrho$ is a sequence of length $k=|\mathit{rear}_{G}|$ such that
$\mathit{rear}_{G}(i)=\mathit{front}_{G}(\varrho(i))$ for all $i\in[k]$.

Now consider $n>0$ and assume, as an induction hypothesis, that the
proposition holds for all graphs with $n-1$ edges. Pick any edge of $G$, say
$e\in\bar{G}$, and let $G^{\prime}$ be the graph obtained from $G$ by removing
$e$ and setting $\mathit{front}_{G^{\prime}}$ to any permutation of
$[\mathit{front}_{G}]\cup[\mathit{att}_{G}(e)]$. Since $G^{\prime}$ has $n-1$
edges, there are $n-1$ atoms $A_{2},\ldots,A_{n}$ and a blank $B$ such that
$G^{\prime}\cong A_{2}\mathop{\odot}\cdots\mathop{\odot}A_{n}\mathop{\odot}B$
by the induction hypothesis. Now let $m=|\mathit{front}_{G}|$,
$k=|\mathit{front}_{G^{\prime}}|$, and
$A_{1}=\langle\mathit{lab}_{G}(e)\rangle^{\varphi}_{\varrho}$ where $\varrho$
is a permutation of $[k]$, and $\varphi$ is a sequence of length $m$ such that
the following holds:
$\mathit{front}_{G^{\prime}}(i)=\mathit{att}_{G}(e,\varrho(i))$ for all
$i\in[k]$ with $\mathit{front}_{G^{\prime}}(i)\in[\mathit{att}_{G}(e)]$.
Moreover, $\varphi(i)=\varrho(j)$ if
$\mathit{front}_{G}(i)=\mathit{front}_{G^{\prime}}(j)$, for all $i\in[m]$ and
$j\in[k]$. It is easy to see that $G\cong A_{1}\mathop{\odot}G^{\prime}\cong
A_{1}\mathop{\odot}\cdots\mathop{\odot}A_{n}\mathop{\odot}B$. ∎

Note that the size of interfaces required to build $G$ according to Lemma 2.3
depends on $G$. Hence, the lemma does not contradict the fact, mentioned in
Section 1, that the set of all graphs composed from a given finite set of
atoms and blanks is of bounded pathwidth.

######  Example 2.2.

Following the construction in the proof, the “star” graph $G$ in Figure 1 can
be composed by $G\cong\langle b\rangle^{1}_{12}\mathop{\odot}\langle
a\rangle^{13}_{123}\mathop{\odot}\langle
a\rangle^{134}_{1234}\mathop{\odot}\langle\varepsilon\rangle^{(4)}_{4}$, all
shown in Figure 1. However, this is not the only composition. A much simpler
one is $G\cong\langle a\rangle^{1}_{1}\mathop{\odot}\langle
a\rangle^{1}_{1}\mathop{\odot}\langle b\rangle^{1}_{2}$.

The example shows that, unlike a string, a graph can be composed from atoms
and blanks in different ways. Moreover, the size of atoms and blanks can also
vary substantially.

##  3 Finite Automata over Graph Symbols

We now follow the idea of Engelfriet and Vereijken [18] to make use of the
close resemblance of graphs under (typed) composition and strings under
concatenation, and denote graphs by strings. Each symbol is interpreted as a
graph, and thus a string translates into a graph, provided that the types of
composed graphs fit. To this end, we type each symbol by a pair $(i,j)$ – the
type of the graph it will represent.

A _typed alphabet_ is a pair $(\mathbf{\Theta},\mathit{type})$ consisting of a
(possibly infinite) set $\mathbf{\Theta}$ of symbols and a function
$\mathit{type}\colon\mathbf{\Theta}\to\mathbb{N}\times\mathbb{N}$ which
assigns a pair $\mathit{type}(a)$ of front and rear ranks to each symbol
$a\in\mathbf{\Theta}$. The pair $(\mathbf{\Theta},\mathit{type})$ is usually
identified with $\mathbf{\Theta}$, and $\mathit{type}$ is kept implicit.

A string $w=a_{1}\cdots a_{n}\in\mathbf{\Theta}^{+}$ is _typed_ if there are
$k_{0},\dots,k_{n}\in\mathbb{N}$ such that
$\mathit{type}(a_{i})=(k_{i-1},k_{i})$ for all $i\in[n]$. We let
$\mathit{type}(w)=(k_{0},k_{n})$. The set of all typed strings over
$\mathbf{\Theta}$ is written $\mathbf{\Theta}^{\oplus}$. The concatenation
$u\cdot v$ of typed strings $u,v\in\mathbf{\Theta}^{\oplus}$ with
$\mathit{type}(u)=(i,j)$ and $\mathit{type}(v)=(m,n)$ is only defined if
$j=m$.

Note that ordinary (untyped) alphabets and strings over them can be considered
as special cases of typed ones by setting $\mathit{type}(a)=(1,1)$ for every
symbol $a$. Further note that there is no empty typed string
$\varepsilon\in\mathbf{\Theta}^{+}$ because its type would be undefined.
Instead, we introduce so-called _blanks_ below.

For a typed alphabet $\mathbf{\Theta}$ and a ranked alphabet $\Sigma$, an
_interpretation operator_
$\left\llbracket\cdot\right\rrbracket\colon\mathbf{\Theta}\to\mathbb{G}_{\Sigma}$
assigns a graph $\left\llbracket a\right\rrbracket\in\mathbb{G}_{\Sigma}$ with
$\mathit{type}(\left\llbracket a\right\rrbracket)=\mathit{type}(a)$ to each
symbol $a\in\mathbf{\Theta}$. We extend $\left\llbracket\cdot\right\rrbracket$
to typed strings over $\mathbf{\Theta}$ by $\left\llbracket a_{1}\cdots
a_{n}\right\rrbracket\cong\left\llbracket
a_{1}\right\rrbracket\mathop{\odot}\cdots\mathop{\odot}\left\llbracket
a_{n}\right\rrbracket$ where $a_{i}\in\mathbf{\Theta}$ for $i\in[n]$.

Every interpretation operator
$\left\llbracket\cdot\right\rrbracket\colon\mathbf{\Theta}\to\mathbb{G}_{\Sigma}$
defines a congruence relation $\sim$ on typed strings, as follows: for all
$u,v\in\mathbf{\Theta}^{\oplus}$, $u\sim v$ if and only if $\left\llbracket
u\right\rrbracket\cong\left\llbracket v\right\rrbracket$.

Given a ranked alphabet $\Sigma$, the _canonical alphabet_
$(\mathbf{\Theta}_{\Sigma},\mathit{type})$ is the typed alphabet given by

$\displaystyle\mathbf{\Theta}_{\Sigma}$
$\displaystyle=\\{a^{\varphi}_{\varrho}\mid\langle
a\rangle^{\varphi}_{\varrho}\text{ is an atom in
$\mathbb{G}_{\Sigma}$}\\}\cup\mathcal{B}$ $\displaystyle\mathcal{B}$
$\displaystyle=\\{\varepsilon^{(n)}_{\varrho}\mid\langle\varepsilon\rangle^{(n)}_{\varrho}\text{
is a blank in $\mathbb{G}_{\Sigma}$}\\}$
$\displaystyle\mathit{type}(a^{\varphi}_{\varrho})$
$\displaystyle=(|\varphi|,|\varrho|)\quad\text{for all
}a^{\varphi}_{\varrho}\in\mathbf{\Theta}_{\Sigma}$
$\displaystyle\mathit{type}(\varepsilon^{(n)}_{\varrho})$
$\displaystyle=(n,|\varrho|)\quad\text{for all
}\varepsilon^{(n)}_{\varrho}\in\mathcal{B}.$

The _canonical interpretation_ of $\mathbf{\Theta}_{\Sigma}$ is given by
$\left\llbracket a^{\varphi}_{\varrho}\right\rrbracket=\langle
a\rangle^{\varphi}_{\varrho}$ for all
$a^{\varphi}_{\varrho}\in\mathbf{\Theta}_{\Sigma}\setminus\mathcal{B}$ and
$\left\llbracket\varepsilon^{(n)}_{\varrho}\right\rrbracket=\langle\varepsilon\rangle^{(n)}_{\varrho}$
for all $\varepsilon^{(n)}_{\varrho}\in\mathcal{B}$. We call all symbols in
$\mathcal{B}$ _blank symbols_ (or just _blanks_), and abbreviate
$\varepsilon^{(n)}_{\varrho}$ with $\varrho=1\cdots n$ as $\varepsilon^{(n)}$.
Note that $\mathcal{B}\subseteq\mathbf{\Theta}_{\Sigma}$ is infinite and
independent of $\Sigma$.

We note the following immediate consequences of the definitions above:

######  Fact 3.1.

The following holds for every ranked alphabet $\Sigma$ and its canonical
alphabet $\mathbf{\Theta}_{\Sigma}$:

  1. 1.

Let $a,b\in\mathbf{\Theta}_{\Sigma}$ with $\mathit{type}(a)=(m,n)$ and
$\mathit{type}(b)=(n,k)$ (for some $m,n,k\in\mathbb{N}$) be such that
$\\{a,b\\}\cap\mathcal{B}\neq\varnothing$. Then $\mathbf{\Theta}_{\Sigma}$
contains a symbol $c$ such that $ab\sim c$. In particular,
$\mathit{type}(c)=(m,k)$. (Note that $c\in\mathcal{B}$ if both $a$ and $b$ are
blanks, and $c\in\mathbf{\Theta}_{\Sigma}\setminus\mathcal{B}$ otherwise.)

  2. 2.

For all $m,n\in\mathbb{N}$ and $a\in\mathbf{\Theta}_{\Sigma}$ with
$\mathit{type}(a)=(n,m)$, we have $\varepsilon^{(n)}a\sim a\sim
a\,\varepsilon^{(m)}$.

By requiring that finite automata respect types, we obtain finite automata
over a finite typed alphabet $\Theta$.

######  Definition 3.2 (Finite Automaton).

Let $\Theta$ be a finite typed alphabet. A _finite automaton_ over $\Theta$ is
a tuple $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ such that $Q$ is a ranked
alphabet of _states_ , $\Delta\subseteq\left(Q\times\Theta\times Q\right)$ is
a set of _transitions_ $(q,a,q^{\prime})$ such that $\mathit{type}(a)=(i,j)$
implies that $\mathit{rank}(q)=i$ and $\mathit{rank}(q^{\prime})=j$, $q_{0}\in
Q$ is the _initial state_ , and $F\subseteq Q\setminus\\{q_{0}\\}$ is a non-
empty set of _final states_ such that
$\mathit{rank}(q)=\mathit{rank}(q^{\prime})$ for all $q,q^{\prime}\in F$.

We let $\mathit{type}(\mathfrak{A})=(m,n)$ where $m=\mathit{rank}(q_{0})$ and
$n=\mathit{rank}(q)$ for all $q\in F$. $\mathfrak{A}$ is _deterministic_ if,
for each pair of transitions $(p,a,q),(p^{\prime},b,q^{\prime})\in\Delta$,
$p=p^{\prime}$ and $a=b$ implies $q=q^{\prime}$.

A _configuration_ of $\mathfrak{A}$ is a pair $(q,w)\in Q\times\Theta^{\ast}$
consisting of the _current state_ $q$ and the _remaining input_ $w$. It is
_initial_ if $q=q_{0}$, and _accepting_ if $q\in F$ and $w=\varepsilon$. Note
that configurations are defined for arbitrary $w\in\Theta^{\ast}$, i.e., $w$
is not necessarily typed.

A transition $\delta=(q,a,q^{\prime})\in\Delta$, where $a$ is a symbol in
$\Theta$, defines _moves_ $(q,aw)\mathrel{\vdash}_{\delta}(q^{\prime},w)$ for
all strings $w\in\Theta^{*}$. We write
$(q,w)\mathrel{\vdash}_{\mathfrak{A}}(q^{\prime},w^{\prime})$ if
$(q,w)\mathrel{\vdash}_{\delta}(q^{\prime},w^{\prime})$ for some transition
$\delta\in\Delta$.

The _language_ accepted by $\mathfrak{A}$ is defined as usual:

$\displaystyle{\mathcal{L}}(\mathfrak{A})=\\{w\in\Theta^{*}\mid\exists q\in
F:(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{*}(q,\varepsilon)\\}.$

Note that ${\mathcal{L}}(\mathfrak{A})\subseteq\Theta^{\oplus}$ because
transitions are typed and $q_{0}\notin F$. In fact, we have
$\mathit{type}(w)=\mathit{type}(\mathfrak{A})$ for all
$w\in{\mathcal{L}}(\mathfrak{A})$.

Associating a graph interpretation operator with $\Theta$, we can recognize
graph languages in the obvious way: a graph $G$ is accepted by an automaton
$\mathfrak{A}$ if $G\cong\left\llbracket w\right\rrbracket$ for some string
$w\in{\mathcal{L}}(\mathfrak{A})$. To enable our automata to work directly on
graphs, we use _graph configurations_ and the corresponding moves:

######  Definition 3.3 (Graph configurations and moves).

Let $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ be a finite automaton with
$\Theta\subseteq\mathbf{\Theta}_{\Sigma}$. A pair $(q,G)$ consisting of a
state $q\in Q$ and a graph $G\in\mathbb{G}_{\Sigma}$ is a _graph
configuration_ , or simply _configuration_ if the context prevents confusion.

A transition $\delta=(q,a,q^{\prime})\in\Delta$ can be applied to a graph
$G\in\mathbb{G}_{\Sigma}$ if there are graphs
$G^{\prime},G_{a}\in\mathbb{G}_{\Sigma}$ such that
$G=G_{a}\mathop{\odot}G^{\prime}$ and $G_{a}\cong\left\llbracket
a\right\rrbracket$. We then call
$(q,G)\mathrel{\Vdash}_{\delta}(q^{\prime},G^{\prime})$ a _move_ (using
$\delta$). We write
$(q,G)\mathrel{\Vdash}_{\mathfrak{A}}(q^{\prime},G^{\prime})$ if
$(q,G)\mathrel{\Vdash}_{\delta}(q^{\prime},G^{\prime})$ for some transition
$\delta\in\Delta$. The set of _acceptable configurations_ of $\mathfrak{A}$
with $\mathit{type}(\mathfrak{A})=(m,n)$ is

$\mathcal{C}_{\mathfrak{A}}=\\{(q,G)\in Q\times\mathbb{G}_{\Sigma}\mid\exists
q^{\prime}\in
F,\,G^{\prime}\in\mathbb{G}_{\Sigma}\colon(q,G)\mathrel{\Vdash}_{\mathfrak{A}}^{\ast}(q^{\prime},G^{\prime})\text{
and }G^{\prime}\cong\langle\varepsilon\rangle^{(n)}_{1\ldots n}\\}.$

The graph language accepted by $\mathfrak{A}$ is then

${\mathcal{L}}_{G}(\mathfrak{A})=\\{G\in\mathbb{G}_{\Sigma}\mid(q_{0},G)\in\mathcal{C}_{\mathfrak{A}}\\}.$

Obviously (and provable by a straightforward induction), we have
${\mathcal{L}}_{G}(\mathfrak{A})=\\{\left\llbracket w\right\rrbracket\mid
w\in{\mathcal{L}}(\mathfrak{A})\\}$. However, given a graph
$G\in{\mathcal{L}}_{G}(\mathfrak{A})$, it is usually not the case that
$w\in{\mathcal{L}}(\mathfrak{A})$ for all $w\in\Theta^{\oplus}$ such that
$\left\llbracket w\right\rrbracket=G$, as demonstrated in the following
example. This turns efficient graph recognition with finite automata into a
nontrivial problem.

$q_{0}$$q_{1}$$q_{2}$$a^{1}_{1}$$a^{1}_{1}$$b^{1}_{2}$ Figure 2: The finite
automaton $\mathfrak{S}$ recognizing the graph language of “stars”.

######  Example 3.1.

Let us consider the graph language of “stars” where each “star” consists of a
center node, which is the only front interface node, and at least two
satellite nodes, which are connected by binary edges with the center node.
Just one of the edges is labeled with $b$, the others with $a$, and the rear
interface consists of just the satellite node attached to the $b$-labeled
edge. Figure 1 shows such a “star”, and Figure 2 the finite automaton
$\mathfrak{S}$ recognizing this graph language. As usual, we draw finite
automata with circles as states and arrows as transitions. The initial state
is indicated by an incoming arrow from nowhere, final states by double
borders. $\mathfrak{S}$ is nondeterministic since it contains a transition
$(q_{0},a^{1}_{1},q_{0})$ as well as $(q_{0},a^{1}_{1},q_{1})$.

One can see that the “star” $G$ in Figure 1 is a member of
${\mathcal{L}}_{G}(\mathfrak{S})$ because the string
$w=a^{1}_{1}\,a^{1}_{1}\,b^{1}_{2}$ is recognized by $\mathfrak{S}$ and
$G\cong\left\llbracket w\right\rrbracket$. Note that $\left\llbracket
w\right\rrbracket\cong\left\llbracket
a^{1}_{1}\right\rrbracket\mathop{\odot}\left\llbracket
a^{1}_{1}\right\rrbracket\mathop{\odot}\left\llbracket
b^{1}_{2}\right\rrbracket=\langle a\rangle^{1}_{1}\mathop{\odot}\langle
a\rangle^{1}_{1}\mathop{\odot}\langle b\rangle^{1}_{2}$, which is one of the
compositions of $G$ shown in Example 2.2, whereas, e.g., the string
$b^{1}_{12}\,a^{13}_{123}\,a^{134}_{1234}\,\varepsilon^{(4)}_{4}$ cannot be
recognized by $\mathfrak{S}$.

##  4 Efficient Graph Recognition with Finite Automata

Let us now use a finite automaton for the recognition of graphs. To achieve
efficiency, we must avoid nondeterminism. To see this, consider a
nondeterministic automaton and a situation where we have reached a
configuration with a state that has several outgoing transitions reading the
same symbol. This means that all of them are applicable whenever one of them
can be applied. Consequently, we must try one of them first, and if this
choice leads into a dead end later, we are forced to backtrack and then try
the next one. Backtracking usually leads to exponential running times, and
should thus be avoided for efficient recognition.

Note that blank transitions, that is, transitions that read a blank, can lead
to nondeterminism, even if the automaton is in fact deterministic. To
understand this, consider a state with at least two outgoing transitions, one
of them a blank transition. Similarly to an epsilon transition in an ordinary
finite automaton, a blank transition (of the right type) can always be
applied. So whenever one of the other transitions is applicable, one must
choose between that transition and the blank transition. If one picks the
“wrong” one that leads into a dead end, backtracking is necessary in order to
choose the other one.

For efficient graph recognition with finite automata, we first develop an
extension of the well-known powerset construction to turn a finite automaton
over a subset of the canonical alphabet into a deterministic one without blank
transitions in places where they may trigger backtracking.

###  4.1 Powerset Construction for Finite Automata

#### General Assumption.

Throughout this subsection, we consider a fixed (ranked) alphabet $\Sigma$,
its canonical alphabet $\mathbf{\Theta}_{\Sigma}$, and a finite automaton
$\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ over a typed alphabet
$\Theta\subset\mathbf{\Theta}_{\Sigma}$. We also let
$(m,n)=\mathit{type}(\mathfrak{A})$.

Input : Finite automaton $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ with
$\Theta\subset\mathbf{\Theta}_{\Sigma}$.

Output : Powerset automaton
$\mathfrak{A}^{\prime}=(\Theta^{\prime},Q^{\prime},\Delta^{\prime},S_{0},F^{\prime})$.

1 $S_{0}\leftarrow\mathop{\textit{Cl}}(q_{0})$ and
$S_{f}\leftarrow\varnothing$

2 $Q^{\prime}\leftarrow\\{S_{0},S_{f}\\}$ and
$F^{\prime}\leftarrow\\{S_{f}\\}$ where
$(\mathit{rank}(S_{0}),\mathit{rank}(S_{f}))=\mathit{type}(\mathfrak{A})$

3 $\Delta^{\prime}\leftarrow\varnothing$

4 $\mathit{frontier}\leftarrow\\{S_{0}\\}$

5 while  _$\mathit{frontier}\neq\varnothing$_ do

6 select and remove any $X$ from $\mathit{frontier}$

7 foreach  _$(\beta,q)\in X$ such that $q\in F$_ do add $(X,\beta,S_{f})$ to
$\Delta^{\prime}$

8
$\psi\leftarrow\\{(a,q^{\prime})\in(\mathbf{\Theta}\setminus\mathcal{B})\times
Q\mid\text{$(\beta,q)\in X$, $(q,b,q^{\prime})\in\Delta$, and $a\sim\beta
b$}\\}$

9 foreach  _$a_{0}\in\mathit{dom}(\psi)$_ do

10 let $\mathit{type}(a_{0})=(i,j)$

11 $Y\leftarrow\mathop{\textit{Cl}}(\psi(a_{0}))$

12 if  _$Y=\beta^{\prime}Y^{\prime}$ for some $Y^{\prime}\in Q^{\prime}$ and
$\beta^{\prime}\in\mathcal{B}$ with $\mathit{type}(\beta^{\prime})=(j,j)$_
then

13 add $(X,a_{1},Y^{\prime})$ to $\Delta^{\prime}$ for some
$a_{1}\in\Theta\setminus\mathcal{B}$ such that $a_{1}\sim a_{0}\beta^{\prime}$

14

15 else

16 let $\mathit{rank}(Y)=j$ and add $Y$ to $Q^{\prime}$ as well as to
$\mathit{frontier}$

17 add $(X,a_{0},Y)$ to $\Delta^{\prime}$

18

19

20

$\Theta^{\prime}\leftarrow\\{a\in\mathbf{\Theta}_{\Sigma}\mid\exists
S,S^{\prime\prime}\in Q^{\prime}:(S,a,S^{\prime})\in\Delta^{\prime}\\}$

Algorithm 1 Powerset construction for a finite automaton.

Algorithm 1 extends the well-known powerset construction and computes a new
automaton whose states are built from sets of states of the input automaton.
As mentioned above, blank transitions resemble epsilon transitions that “read”
the empty word. However, blanks are more complicated because they must take
nodes into account; remember that the rear interface of a blank can contain a
subset of its nodes in any order (cf. Figure 1). Therefore, Algorithm 1
considers pairs of the form $(\beta,q)$ where $\beta$ is a blank and $q$ a
state of the input automaton. Informally speaking, such a pair indicates that
one can reach state $q$ after reading $\beta$. Note that $\beta$ can be
$\varepsilon^{(i)}$ for an appropriate $i$, that is, an identity without any
effect (which is comparable to $\varepsilon$ in the string case). The states
of the computed automaton then consist of sets of such pairs.

When building these sets, the algorithm must follow any sequence of blank
transitions and combine their blanks into a single blank, which is always
possible thanks to Fact 3.1. We call the set of all states (together with
these blanks) that can be reached from a state $q\in Q$ by a sequence of blank
transitions the _closure_ of $q$. It is defined as

$\mathop{\textit{Cl}}(q)=\\{(\beta,q^{\prime})\in\mathcal{B}\times
Q\mid\exists\sigma\in\mathcal{B}^{\ast}\colon(q,\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q^{\prime},\varepsilon)\text{
and }\varepsilon^{(i)}\beta\sim\varepsilon^{(i)}\sigma\\}$

where $\mathit{rank}(q)=i$. The condition
$\varepsilon^{(i)}\beta\sim\varepsilon^{(i)}\sigma$ in this definition can be
simplified to $\beta\sim\sigma$ unless $\sigma=\varepsilon$. If
$\sigma=\varepsilon$ then $\varepsilon^{(i)}$ is required because
$\left\llbracket\varepsilon\right\rrbracket$ is undefined. Note also that
$(\varepsilon^{(i)},q)\in\mathop{\textit{Cl}}(q)$, and that
$(\beta,q^{\prime})\in\mathop{\textit{Cl}}(q)$ implies
$\mathit{type}(\beta)=(i,\mathit{rank}(q^{\prime}))$.

We extend the definition of closures to sets of states by defining
$\mathop{\textit{Cl}}(M)=\bigcup_{q\in M}\mathop{\textit{Cl}}(q)$ for all
$M\subseteq Q$ as used in Line 1. For every set $C\subseteq\mathcal{B}\times
Q$ and $i\in\mathbb{N}$ such that $(\beta^{\prime},q)\in C$ implies
$\mathit{type}(\beta^{\prime})=(i,\mathit{rank}(q))$, and every blank
$\beta\in\mathcal{B}$ of type $(i,i)$, we define

$\beta C=\\{(\beta^{\prime\prime},q)\in\mathcal{B}\times
Q\mid\text{$\exists\beta^{\prime}\in\mathcal{B}\colon(\beta^{\prime},q)\in C$
and $\beta^{\prime\prime}\sim\beta\beta^{\prime}$}\\}$

as used in Line 1. Note that a blank $\beta^{\prime\prime}$ with
$\beta^{\prime\prime}\sim\beta\beta^{\prime}$ always exists, thanks to Fact
3.1.1.

We now prove the correctness of Algorithm 1 by first showing that it always
terminates and produces a proper finite automaton as a result. After that, we
will show that the produced powerset automaton is equivalent to the input
automaton.

######  Lemma 4.1.

Algorithm 1 terminates for every finite automaton
$\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ and outputs a finite automaton.

###### Proof.

We use the notations established in Algorithm 1. In particular,
$\mathfrak{A}^{\prime}=(\Theta^{\prime},Q^{\prime},\Delta^{\prime},S_{0},F^{\prime})$
is the output of the algorithm.

Every state in $Q^{\prime}$ is a subset of $\mathcal{B}\times Q$. The fact
that $Q$ and $\Theta$ are finite thus implies that $Q^{\prime}$ is finite.
Since no element of $Q^{\prime}$ is added to $\mathit{frontier}$ more than
once, none of the loops of Algorithm 1 can run endlessly.

It remains to be shown that the transitions of $\mathfrak{A}^{\prime}$ are
correctly typed. For this, we consider any transition
$\delta=(S,a,S^{\prime})\in\Delta^{\prime}$ and show that
$\mathit{type}(a)=(\mathit{rank}(S),\mathit{rank}(S^{\prime}))$. Transition
$\delta$ must have been added in Lines 1, 1, or 1. Before we consider each of
these cases, first note that each state $S\neq S_{f}$ is a non-empty set of
pairs $(\beta,q)\in\mathcal{B}\times Q$ that satisfy
$\mathit{type}(\beta)=(\mathit{rank}(S),\mathit{rank}(q))$ by the definition
of closures, how $\psi$ is computed in Line 1, and how $\mathit{rank}(S)$ is
set in Lines 1 and 1. Further note that we have $\mathit{rank}(X)=i$ when Line
1 is reached, also by the definition of closures and how $\psi$ is computed.
We now distinguish the three cases where $\delta$ may have been added to
$\Delta^{\prime}$:

  * •

Line 1: Since $(\beta,q)\in X$ and $q\in F$,
$\mathit{type}(\beta)=(\mathit{rank}(X),\mathit{rank}(q))=(\mathit{rank}(X),\mathit{rank}(S_{f}))$

  * •

Line 1: $\mathit{rank}(Y^{\prime})=j$ and $\mathit{type}(a_{1})=(i,j)$ follow
from $Y=\beta^{\prime}Y^{\prime}$, $\mathit{type}(\beta^{\prime})=(j,j)$, and
$\mathit{type}(a_{0})=(i,j)$, and hence
$\mathit{type}(a_{1})=(\mathit{rank}(X),\mathit{rank}(Y^{\prime}))$.

  * •

Line 1: $\mathit{rank}(Y)$ is set to $j$, and hence
$\mathit{type}(a_{0})=(\mathit{rank}(X),\mathit{rank}(Y))$,

Hence, the transitions in $\Delta^{\prime}$ are correctly typed, i.e.,
$\mathfrak{A}^{\prime}$ is a finite automaton. ∎

To prove that the powerset automation $\mathfrak{A}^{\prime}$ produced by
Algorithm 1 is equivalent to its input automaton $\mathfrak{A}$, we now show
that every accepting sequence of moves in $\mathfrak{A}$ has a corresponding
sequence of moves in $\mathfrak{A}^{\prime}$ (Lemma 4.3) and vice versa (Lemma
4.4). For proving Lemma 4.3, we will need the following auxiliary result.
Informally speaking (and ignoring the fact that we are actually dealing with
pairs $(\beta,q)$ instead of just states $q$), Lemma 4.2 proves that every
state reachable from a closure state by a blank transition is also contained
in the closure:

######  Lemma 4.2.

Let $q,q^{\prime},q^{\prime\prime}\in Q$,
$\beta,\beta^{\prime},\beta^{\prime\prime}\in\mathcal{B}$, and
$\delta=(q^{\prime},\beta^{\prime},q^{\prime\prime})\in\Delta$. If
$(\beta,q^{\prime})\in\mathop{\textit{Cl}}(q)$ and
$\beta^{\prime\prime}\sim\beta\beta^{\prime}$ then
$(\beta^{\prime\prime},q^{\prime\prime})\in\mathop{\textit{Cl}}(q)$.

###### Proof.

Let $\mathit{rank}(q)=i$. By the definition of $\mathop{\textit{Cl}}(q)$,
$(\beta,q^{\prime})\in\mathop{\textit{Cl}}(q)$ implies
$(q,\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q^{\prime},\varepsilon)$ and
$\varepsilon^{(i)}\beta\sim\varepsilon^{(i)}\sigma$ for some
$\sigma\in\mathcal{B}^{\ast}$. Consequently,
$(q,\sigma\beta^{\prime})\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q^{\prime},\beta^{\prime})\mathrel{\vdash}_{\delta}(q^{\prime\prime},\varepsilon)$
and
$\varepsilon^{(i)}\sigma\beta^{\prime}\sim\varepsilon^{(i)}\beta\beta^{\prime}\sim\varepsilon^{(i)}\beta^{\prime\prime}$,
and thus $(\beta^{\prime\prime},q^{\prime\prime})\in\mathop{\textit{Cl}}(q)$.
∎

######  Lemma 4.3.

Consider $q\in Q$ and $w\in\Theta^{\ast}$ such that
$(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$. Then there
exist $w^{\prime}\in\Theta^{\ast}$, $S\in Q^{\prime}$, and
$\beta\in\mathcal{B}$ such that
$(S_{0},w^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\varepsilon)$,
$(\beta,q)\in S$, and
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime}\beta$.222Recall that
$\mathit{type}(\mathfrak{A})=(m,n)$.

###### Proof.

We prove the proposition by induction over the length $\ell$ of the move
sequence $(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$. The
proposition is clearly true for $\ell=0$ (with $w=w^{\prime}=\varepsilon$,
$S=S_{0}$, and $\beta=\varepsilon^{(m)}$). For $\ell>0$, we consider the
sequence
$(q_{0},wa)\mathrel{\vdash}_{\mathfrak{A}}^{\ell-1}(q,a)\mathrel{\vdash}_{\delta}(q^{\prime},\varepsilon)$
using transition $\delta=(q,a,q^{\prime})\in\Delta$. By the induction
hypothesis, there is a sequence
$(S_{0},w^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\varepsilon)$
with $(\beta,q)\in S$ and
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime}\beta$. We have to show that
there is also a sequence
$(S_{0},w^{\prime}a^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S^{\prime},\varepsilon)$
with $(\gamma,q^{\prime})\in S^{\prime}$ and
$\varepsilon^{(m)}wa\sim\varepsilon^{(m)}w^{\prime}a^{\prime}\gamma$. We
distinguish two cases:

  * •

$a\in\mathcal{B}$: By Lines 1, 1, and 1 of Algorithm 1,
$(\beta,q)\in\mathop{\textit{Cl}}(q^{\prime\prime})\subseteq S$ for some
$q^{\prime\prime}\in Q$. Let $\beta^{\prime}\in\mathcal{B}$ such that
$\beta^{\prime}\sim\beta a$. We have
$(\beta^{\prime},q^{\prime})\in\mathop{\textit{Cl}}(q^{\prime\prime})\subseteq
S$ by Lemma 4.2 and $\varepsilon^{(m)}wa\sim\varepsilon^{(m)}w^{\prime}\beta
a\sim\varepsilon^{(m)}w^{\prime}\beta^{\prime}$ by the induction hypothesis
and the definition of $\beta^{\prime}$. This proves the proposition by
choosing $a^{\prime}=\varepsilon$ and $\gamma=\beta^{\prime}$.

  * •

$a\in\Theta\setminus\mathcal{B}$: Whenever an element is added to
$Q^{\prime}$, it is also added to $\mathit{frontier}$ (Line 1 and Line 1).
Since $S\in Q^{\prime}$ and $\mathit{frontier}=\varnothing$ when Algorithm 1
terminates, $S$ must have been selected as $X$ in Line 1 at some point. As
$(\beta,q)\in S$ and $\delta=(q,a,q^{\prime})\in\Delta$, there is a
$b\in\Theta\setminus\mathcal{B}$ such that $b\sim\beta a$,
$(b,q^{\prime})\in\psi$ after executing Line 1, and
$(\varepsilon^{(j)},q^{\prime})\in Y$ after executing Line 1, and after
selecting $b$ as $a_{0}$ in Line 1. $Y$ is handled in one of two sub-cases
selected in Lines 1 and 1:

    * –

Line 1, i.e., $Q^{\prime}$ already contains a similar nonterminal $Y^{\prime}$
such that $Y=\beta^{\prime}Y^{\prime}$ for some blank
$\beta^{\prime}\in\mathcal{B}$ with $\mathit{type}(\beta^{\prime})=(j,j)$, and
$\delta^{\prime}=(X,b^{\prime},Y^{\prime})=(S,b^{\prime},Y^{\prime})$ is added
to $\Delta^{\prime}$ where $b^{\prime}\in\Theta\setminus\mathcal{B}$ and
$b^{\prime}\sim b\beta^{\prime}=a_{0}\beta^{\prime}$. Consequently,
$(S_{0},w^{\prime}b^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,b^{\prime})\mathrel{\vdash}_{\delta^{\prime}}(Y^{\prime},\varepsilon)$.
Since $(\varepsilon^{(j)},q^{\prime})\in Y$, there exists
$\beta^{\prime\prime}\in\mathcal{B}$ such that
$(\beta^{\prime\prime},q^{\prime})\in Y^{\prime}$ and
$\varepsilon^{(j)}\sim\beta^{\prime}\beta^{\prime\prime}$. Therefore,

$\varepsilon^{(m)}wa\sim\varepsilon^{(m)}w^{\prime}\beta
a\sim\varepsilon^{(m)}w^{\prime}b\sim\varepsilon^{(m)}w^{\prime}b\varepsilon^{(j)}\sim\varepsilon^{(m)}w^{\prime}b\beta^{\prime}\beta^{\prime\prime}\sim\varepsilon^{(m)}w^{\prime}b^{\prime}\beta^{\prime\prime}$

by the induction hypothesis, the construction of $b$ and $b^{\prime}$, and the
fact that $\varepsilon^{(j)}\sim\beta^{\prime}\beta^{\prime\prime}$. This
proves the proposition by choosing $a^{\prime}=b^{\prime}$,
$\gamma=\beta^{\prime\prime}$, and $S^{\prime}=Y^{\prime}$.

    * –

Line 1, i.e., $Y$ is not already in $Q^{\prime}$, and neither is there a
similar one. Thus, $Y$ is added to $Q^{\prime}$ and
$\delta^{\prime}=(X,b,Y)=(S,b,Y)$ is added to $\Delta^{\prime}$. Consequently,
$(S_{0},w^{\prime}b)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(S,b)\mathrel{\vdash}_{\delta^{\prime}}(Y,\varepsilon)$
and $\varepsilon^{(m)}wa\sim\varepsilon^{(m)}w^{\prime}\beta
a\sim\varepsilon^{(m)}w^{\prime}b$ by the induction hypothesis and the
construction of $b$. This proves the proposition with $a^{\prime}=b$,
$\gamma=\varepsilon$, and $S^{\prime}=Y$.∎

######  Lemma 4.4.

Let $S\in Q^{\prime}$, $\beta\in\mathcal{B}$, $q\in Q$, and
$w^{\prime}\in\Theta^{\ast}$ be such that $(\beta,q)\in S$ and
$(S_{0},w^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\varepsilon)$.
Then there exists $w\in\Theta^{\ast}$ such that
$(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$ and
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime}\beta$.

###### Proof.

We prove the proposition by induction over the length $\ell$ of the move
sequence
$(S_{0},w^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\varepsilon)$.
For $\ell=0$, we have
$(S_{0},\varepsilon)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{0}(S_{0},\varepsilon)$.
Consider any $(\beta,q)\in S_{0}$. $S_{0}=\mathop{\textit{Cl}}(q_{0})$ implies
$(q_{0},\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$ for some
$\sigma\in\mathcal{B}^{\ast}$ such that
$\varepsilon^{(m)}\sigma\sim\varepsilon^{(m)}\beta$. This proves the
proposition by choosing $w^{\prime}=\varepsilon$ and $w=\sigma$.

For $\ell>0$, the sequence
$(S_{0},w^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\varepsilon)$
has the form
$(S_{0},w_{0}^{\prime}a)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ell-1}(S^{\prime},a)\mathrel{\vdash}_{\delta}(S,\varepsilon)$,
where $w^{\prime}=w_{0}^{\prime}a$ and
$\delta=(S^{\prime},a,S)\in\Delta^{\prime}$. By the induction hypothesis, for
every $(\gamma,q^{\prime})\in S^{\prime}$, there is $w_{0}\in\Theta^{\ast}$
such that
$(q_{0},w_{0})\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q^{\prime},\varepsilon)$
and $\varepsilon^{(m)}w_{0}\sim\varepsilon^{(m)}w_{0}^{\prime}\gamma$. We show
that $(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$ for some
$w\in\Theta^{\ast}$ such that
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w_{0}^{\prime}a\beta$. This will
complete the proof because $w^{\prime}=w_{0}^{\prime}a$.

Transition $\delta=(S^{\prime},a,S)$ must have been added to $\Delta^{\prime}$
in one of the two cases selected in Lines 1 or 1.

  * •

Line 1: $\delta=(S^{\prime},a,S)$ has been added to $\Delta^{\prime}$ after
$S^{\prime}$ had been selected as $X$ in Line 1, a terminal
$a_{0}\in\Theta\setminus\mathcal{B}$ had been selected in Line 1, $Y$ had been
computed in Line 1, and $S=Y^{\prime}$ had been identified by
$Y=\beta^{\prime}Y^{\prime}$ for some blank $\beta^{\prime}\in\mathcal{B}$
with $\mathit{type}(\beta^{\prime})=(j,j)$ and $a\sim a_{0}\beta^{\prime}$.
Since $(\beta,q)\in S=Y^{\prime}$, $Y=\beta^{\prime}Y^{\prime}$ must contain
some $(\gamma_{0},q)$ with $\gamma_{0}\sim\beta^{\prime}\beta$. There must be
a state $q^{\prime\prime}\in Q$ such that
$(\gamma_{0},q)\in\mathop{\textit{Cl}}(q^{\prime\prime})$ and
$q^{\prime\prime}\in\psi(a_{0})$, where $\psi$ is computed in Line 1, because
$(\gamma_{0},q)\in Y$. By the definition of $\mathop{\textit{Cl}}(X)$,
$(\gamma_{0},q)\in\mathop{\textit{Cl}}(q^{\prime\prime})$ implies
$(q^{\prime\prime},\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$
for some $\sigma\in\mathcal{B}^{\ast}$ such that
$\varepsilon^{(j)}\sigma\sim\varepsilon^{(j)}\gamma_{0}$. By the definition of
$\psi$, there must be a transition $(q^{\prime},b,q^{\prime\prime})\in\Delta$
and $(\gamma,q^{\prime})\in S^{\prime}=X$ such that $a_{0}\sim\gamma b$ and
thus
$(q_{0},w_{0}b\sigma)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(q^{\prime},b\sigma)\mathrel{\vdash}_{\mathfrak{A}}(q^{\prime\prime},\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$
by the induction hypothesis for some $w_{0}\in\Theta^{\ast}$ such that
$\varepsilon^{(m)}w_{0}^{\prime}\gamma\sim\varepsilon^{(m)}w_{0}$. Therefore,

$\varepsilon^{(m)}w_{0}b\sigma\sim\varepsilon^{(m)}w_{0}^{\prime}\gamma
b\sigma\sim\varepsilon^{(m)}w_{0}^{\prime}a_{0}\sigma\sim\varepsilon^{(m)}w_{0}^{\prime}a_{0}\gamma_{0}\sim\varepsilon^{(m)}w_{0}^{\prime}a_{0}\beta^{\prime}\beta\sim\varepsilon^{(m)}w_{0}^{\prime}a\beta.$

This proves the statement of the lemma in this case by choosing
$w=w_{0}b\sigma$.

  * •

Line 1: $\delta=(S^{\prime},a,S)$ has been added to $\Delta^{\prime}$ after
$S^{\prime}$ had been selected as $X$ in Line 1 and $S=Y$ had been computed in
Line 1 after selecting $a$ as $a_{0}$ in Line 1. There must be a state
$q^{\prime\prime}\in Q$ such that
$(\beta,q)\in\mathop{\textit{Cl}}(q^{\prime\prime})$ and
$(a,q^{\prime\prime})\in\psi$ computed in Line 1 because $(\beta,q)\in S=Y$.
Similar to the previous case,
$(\beta,q)\in\mathop{\textit{Cl}}(q^{\prime\prime})$ implies
$(q^{\prime\prime},\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$
for some $\sigma\in\mathcal{B}^{\ast}$ such that
$\varepsilon^{(j)}\sigma\sim\varepsilon^{(j)}\beta$. By the definition of
$\psi$, there must be a transition $(q^{\prime},b,q^{\prime\prime})\in\Delta$
and $(\gamma,q^{\prime})\in S^{\prime}=X$ with $a\sim\gamma b$ and thus
$(q_{0},w_{0}b\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q^{\prime},b\sigma)\mathrel{\vdash}_{\mathfrak{A}}(q^{\prime\prime},\sigma)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$
by the induction hypothesis for some $w_{0}\in\Theta^{\ast}$ such that
$\varepsilon^{(m)}w_{0}^{\prime}\gamma\sim\varepsilon^{(m)}w_{0}$. Therefore,

$\varepsilon^{(m)}w_{0}b\sigma\sim\varepsilon^{(m)}w_{0}^{\prime}\gamma
b\sigma\sim\varepsilon^{(m)}w_{0}^{\prime}a\sigma\sim\varepsilon^{(m)}w_{0}^{\prime}a\beta.$

This proves the statement in this case, and thus completes the proof of the
lemma, by setting $w=w_{0}b\sigma$.∎

We are now ready to prove the equivalence of a finite automaton and its
powerset automaton using the following notion of equivalence:

######  Definition 4.5 (Equivalent automata).

Two finite automata of the same type $(m,n)$ are _equivalent_ if the following
holds: for every $w\in{\mathcal{L}}(\mathfrak{A})$ there exists
$w^{\prime}\in{\mathcal{L}}(\mathfrak{A}^{\prime})$ such that
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime}$, and for every
$w^{\prime}\in{\mathcal{L}}(\mathfrak{A}^{\prime})$ there exists
$w\in{\mathcal{L}}(\mathfrak{A})$ such that
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime}$.

######  Theorem 4.6.

$\mathfrak{A}$ and the powerset automaton $\mathfrak{A}^{\prime}$ computed
from $\mathfrak{A}$ by Algorithm 1 are equivalent.

###### Proof.

We have to prove both implications in Definition 4.5. To prove the first
implication, let $w\in\Theta^{\ast}$ and consider a sequence
$(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$ with $q\in
F$. By Lemma 4.3, there exist $w^{\prime\prime}\in\Theta^{\ast}$, $S\in
Q^{\prime}$, and $\beta\in\mathcal{B}$ such that
$(S_{0},w^{\prime\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\varepsilon)$,
$(\beta,q)\in S$, and
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime\prime}\beta$. Since $S\in
Q^{\prime}$, $S$ must have been selected as $X$ in Line 1 at some point. Since
$q\in F$ and $(\beta,q)\in S$, a transition $(S,\beta,S_{f})$ has been added
to $\Delta^{\prime}$ in Line 1, and thus
$(S_{0},w^{\prime\prime}\beta)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\beta)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}(S_{f},\varepsilon)$,
i.e., $w^{\prime\prime}\beta\in{\mathcal{L}}(\mathfrak{A}^{\prime})$, which
proves the first implication by choosing $w^{\prime}=w^{\prime\prime}\beta$.

Now consider any $w^{\prime}\in\Theta^{*}$ and a sequence
$(S_{0},w^{\prime})\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S_{f},\varepsilon)$.
Since $S_{f}$ can only be reached by transitions added in Line 1, this
sequence must have the form
$(S_{0},w^{\prime\prime}\beta)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}^{\ast}(S,\beta)\mathrel{\vdash}_{\mathfrak{A}^{\prime}}(S_{f},\varepsilon)$
for some $S\in q^{\prime}$, $w^{\prime\prime}\in\Theta^{\ast}$, $q\in F$, and
$\beta\in\mathcal{B}$ such that $w^{\prime}=w^{\prime\prime}\beta$ and
$(\beta,q)\in S$. By Lemma 4.4, there is a $w\in\Theta^{\ast}$ such that
$(q_{0},w)\mathrel{\vdash}_{\mathfrak{A}}^{\ast}(q,\varepsilon)$ and
$\varepsilon^{(m)}w\sim\varepsilon^{(m)}w^{\prime\prime}\beta=\varepsilon^{(m)}w^{\prime}$,
which proves the other implication. ∎

###  4.2 Making the Powerset Automaton Deterministic

Since Algorithm 1 resembles the classical powerset construction, one might
assume that the resulting powerset automaton is deterministic, but this is not
always the case, demonstrated by the following example:

######  Example 4.1.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$a^{12}_{12}$$b^{12}_{21}$$b^{12}_{12}$$\varepsilon^{(2)}_{21}$$\varepsilon^{(2)}_{21}$
Figure 3: Automaton $\mathfrak{B}$ of Example 4.1.

$S_{0}$$S_{1}$$S_{2}$$S_{f}$$a^{12}_{12}$$b^{12}_{12}$$b^{12}_{12}$$\varepsilon^{(2)}$$\varepsilon^{(2)}$
Figure 4: Nondeterministic automaton $\mathfrak{B}^{\prime}$ produced from
$\mathfrak{B}$ by Algorithm 1.

Let $a$ and $b$ be symbols of rank 2, and consider the finite automaton
$\mathfrak{B}$ shown in Figure 4 as input to Algorithm 1. Before the first
iteration of the while loop beginning at Line 1 starts, we have
$S_{0}=\\{(\varepsilon^{(2)}_{12},q_{0})\\}$, $Q^{\prime}=\\{S_{0},S_{f}\\}$,
$\Delta^{\prime}=\varnothing$, and $\mathit{frontier}=\\{S_{0}\\}$. The first
iteration of the while loop then selects $X=S_{0}$ and computes
$\psi=\\{(a^{12}_{12},q_{1}),(b^{12}_{21},q_{2}),(b^{12}_{12},q_{3})\\}$. The
nested foreach loop has the following iterations:

  1. 1.

$a_{0}=a^{12}_{12}$ and
$Y=\\{(\varepsilon^{(2)}_{12},q_{1}),(\varepsilon^{(2)}_{21},q_{2})\\}$. Lines
1 and 1 add $Y$ as a new state $S_{1}$ to $Q^{\prime}$ and
$(S_{0},a^{12}_{12},S_{1})$ to $\Delta^{\prime}$.

  2. 2.

$a_{0}=b^{12}_{21}$ and
$Y=\\{(\varepsilon^{(2)}_{12},q_{2}),(\varepsilon^{(2)}_{21},q_{1})\\}$. Since
$Y=\varepsilon^{(2)}_{21}S_{1}$, Line 1 computes $a_{1}=b^{12}_{12}$ because
$b^{12}_{12}\sim b^{12}_{21}\,\varepsilon^{(2)}_{21}$, and adds
$(S_{0},b^{12}_{12},S_{1})$ to $\Delta^{\prime}$.

  3. 3.

$a_{0}=b^{12}_{12}$ and $Y=\\{(\varepsilon^{(2)}_{12},q_{3})\\}$. Lines 1 and
1 add $Y$ as a new state $S_{2}$ to $Q^{\prime}$ and
$(S_{0},b^{12}_{12},S_{2})$ to $\Delta^{\prime}$.

Algorithm 1 terminates after adding $(S_{1},\varepsilon^{(2)}_{12},S_{f})$ and
$(S_{2},\varepsilon^{(2)}_{12},S_{f})$ to $\Delta^{\prime}$ with
$Q^{\prime}=\\{S_{0},S_{1},S_{2},\allowbreak S_{f}\\}$. Figure 4 shows the
resulting automaton $\mathfrak{B}^{\prime}$. We have
$(S_{0},b^{12}_{12},S_{1}),(S_{0},b^{12}_{12},S_{2})\in\Delta^{\prime}$, that
is, $\mathfrak{B}^{\prime}$ is nondeterministic.∎

The reason for the nondeterminism of the resulting automaton is apparently the
use of the atoms $b^{12}_{12}$ and $b^{12}_{21}$, which is problematic because
$b^{12}_{12}\sim b^{12}_{21}\,\varepsilon^{(2)}_{21}$. Let us call automata
that use such symbols _ambiguous_ :

######  Definition 4.7 (Ambiguous finite automata).

A finite automaton $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ is _ambiguous_ if
there are symbols $a,a^{\prime}\in\Theta\setminus\mathcal{B}$ such that $a\neq
a^{\prime}$ and $a\beta\sim a^{\prime}\beta^{\prime}$ for some
$\beta,\beta^{\prime}\in\mathcal{B}$ (i.e., $\left\llbracket
a\right\rrbracket$ and $\left\llbracket a^{\prime}\right\rrbracket$ differ
only in their rears). $\mathfrak{A}$ is called _unambiguous_ if it is not
ambiguous.

Note that the automaton defined in Example 4.1 is ambiguous by this definition
because $b^{12}_{21}\,\varepsilon^{(2)}_{21}\sim b^{12}_{12}\sim
b^{12}_{12}\,\varepsilon^{(2)}_{12}$.

######  Theorem 4.8.

The powerset automaton $\mathfrak{A^{\prime}}$ computed by Algorithm 1 is
deterministic if $\mathfrak{A}$ is unambiguous.

###### Proof.

Consider any unambiguous automaton $\mathfrak{A}$, and assume that Algorithm 1
produces a nondeterministic automaton $\mathfrak{A}^{\prime}$, i.e., there are
two transitions $\delta=(S,a,S^{\prime})\in\Delta^{\prime}$ and
$\delta^{\prime}=(S,a,S^{\prime\prime})\in\Delta^{\prime}$ such that
$S^{\prime}\neq S^{\prime\prime}$. Note that we have target state $S_{f}$ and
$\beta\in\mathcal{B}$ for all transitions added to $\Delta^{\prime}$ in Line
1, and $Y\neq S_{f}$, $Y^{\prime}\neq S_{f}$, $a_{0}\notin\mathcal{B}$, as
well as $a_{1}\notin\mathcal{B}$ for all transitions added in Lines 1 and 1,
respectively. Consequently, neither $\delta$ nor $\delta^{\prime}$ can have
been added by Line 1, and both of them must have been added within the same
iteration of the while loop using the same set $\psi$ computed in Line 1, but
in different iterations of the foreach loop that have selected, say, $c_{1}$
and $c_{2}$ as $a_{0}$, respectively. If $\delta$ has been added to
$\Delta^{\prime}$ in Line 1, we have $a\sim c_{1}\beta_{1}$ for some
$\beta_{1}\in\mathcal{B}$, and $a=c_{1}$ if $\delta$ has been added in Line 1.
Similarly, $a\sim c_{2}\beta_{2}$ for some $\beta_{1}\in\mathcal{B}$, or
$a=c_{2}$. We have $c_{1}\neq c_{2}$ because $c_{1}$ and $c_{2}$ have been
selected in different foreach loop iterations. Hence, either $c_{1}\sim
c_{2}\beta_{2}$, $c_{1}\beta_{1}\sim c_{2}$, or $c_{1}\beta_{1}\sim
c_{2}\beta_{2}$, in contradiction to $\mathfrak{A}$ being unambiguous. ∎

######  Example 4.2.

$S_{0}$$S_{1}$$S_{2}$$S_{f}$$a^{1}_{1}$$\delta_{1}$$b^{1}_{2}$$\delta_{3}$$a^{1}_{1}$$\delta_{2}$$\varepsilon^{(1)}$$\delta_{4}$
Figure 5: The deterministic automaton $\mathfrak{S}^{\prime}$ obtained from
$\mathfrak{S}$ (Figure 2) by Algorithm 1.

The automaton $\mathfrak{S}$ shown in Figure 2 is unambiguous, and Algorithm 1
thus computes a deterministic finite automaton (DFA) $\mathfrak{S}^{\prime}$
shown in Figure 5. The states of $\mathfrak{S}^{\prime}$ are
$S_{0}=\\{(\varepsilon^{(1)},q_{0})\\}$,
$S_{1}=\\{(\varepsilon^{(1)},q_{0}),(\varepsilon^{(1)},q_{1})\\}$,
$S_{2}=\\{\varepsilon^{(1)},q_{2})\\}$, and $S_{f}=\varnothing$.

The restriction to unambiguous automata is in fact insignificant for automata
over subsets of the canonical alphabet $\mathbf{\Theta}_{\Sigma}$ (and its
canonical interpretation). One can easily transform an automaton
$\mathfrak{A}$ into an equivalent unambiguous one using the following
iterative process:

Consider an automaton $\mathfrak{A}$ that has
$a,a^{\prime}\in\Theta\setminus\mathcal{B}$ such that $a\neq a^{\prime}$ and
$a\beta\sim a^{\prime}\beta^{\prime}$ for some
$\beta,\beta^{\prime}\in\mathcal{B}$. Since we use the canonical
interpretation of symbols in $\mathbf{\Theta}_{\Sigma}$, $a$ and $a^{\prime}$
must have the form $a=b^{\varphi}_{\varrho}$ and
$a^{\prime}=b^{\varphi}_{\varrho^{\prime}}$ using the same label
$b\in\bar{\Sigma}$ and front interface $\varphi$, that is, $a$ and
$a^{\prime}$ differ only in their rear interfaces. Hence, one can identify a
more general rear interface $\hat{\varrho}$ such that $a\sim
b^{\varphi}_{\hat{\varrho}}\,\hat{\beta}$ and $a^{\prime}\sim
b^{\varphi}_{\hat{\varrho}}\,\hat{\beta}^{\prime}$ for some blanks
$\hat{\beta}$ and $\hat{\beta}^{\prime}$. $\mathfrak{A}^{\prime}$ is then
obtained from $\mathfrak{A}$ by removing $a$ and $a^{\prime}$ from $\Theta$
and adding $b^{\varphi}_{\hat{\varrho}},\hat{\beta}$, and
$\hat{\beta}^{\prime}$. Furthermore, every transition $(q,a,q^{\prime})$ in
$\Delta$ is replaced by two transitions
$(q,b^{\varphi}_{\hat{\varrho}},q^{\prime\prime})$ and
$(q^{\prime\prime},\hat{\beta},q^{\prime})$ where $q^{\prime\prime}$ is a new
state with $\mathit{rank}(q^{\prime\prime})=|\hat{\varrho}|$ that is also
added to $Q$, and proceeds similarly for each transition referring to
$a^{\prime}$. This process is continued until $\mathfrak{A}^{\prime}$ is
finally unambiguous.

######  Example 4.3.

$q_{0}$$q_{3}^{\prime}$$q_{3}$$q_{2}^{\prime}$$q_{2}$$q_{1}$$a^{12}_{12}$$b^{12}_{12}$$b^{12}_{12}$$\varepsilon^{(2)}_{21}$$\varepsilon^{(2)}_{21}$$\varepsilon^{(2)}$$\varepsilon^{(2)}_{21}$
Figure 6: Unambiguous automaton $\mathfrak{B}^{\prime\prime}$ obtained from
$\mathfrak{B}$ (Example 4.1).

$S_{0}$$S_{1}$$S_{f}$$S_{2}$$a^{12}_{12}$$b^{12}_{12}$$\varepsilon^{(2)}$$\varepsilon^{(2)}$
Figure 7: Automaton $\mathfrak{B}_{\mathrm{d}}$ obtained from
$\mathfrak{B}^{\prime\prime}$ by Algorithm 1.

Figure 7 shows the unambiguous automaton $\mathfrak{B}^{\prime\prime}$
obtained from $\mathfrak{B}$ in Example 4.1 using the procedure sketched
above. The ambiguous transitions $(q_{0},b^{12}_{21},q_{2})$ and
$(q_{0},b^{12}_{12},q_{3})$ of $\mathfrak{B}$ have been split into four
transitions with new intermediate states $q_{2}^{\prime}$ and
$q_{3}^{\prime}$. Algorithm 1 now produces the DFA $\mathfrak{B}_{\mathrm{d}}$
shown in Figure 7 when applied to $\mathfrak{B}^{\prime\prime}$.

###  4.3 Selecting Promising Transitions

Let us now consider the DFA $\mathfrak{A}_{\mathrm{d}}$ that has been produced
by Algorithm 1, and use it for recognizing a valid graph
$G\in{\mathcal{L}}_{G}(\mathfrak{A}_{\mathrm{d}})$ using graph moves. First
note that $\mathfrak{A}_{\mathrm{d}}$ does not have any blank transitions
except those that go into the final state, which does not have any outgoing
transitions at all. Consequently, blank transitions are only applied when the
remaining input is isomorphic to the corresponding blank graph, that is, there
is no choice when such transitions have to be applied. Despite determinism,
this is not necessarily the case for the other transitions. Consider the
situation where we have reached a configuration $(s,G)$ and $G$ contains some
edges. Although $\mathfrak{A}_{\mathrm{d}}$ is deterministic, several
transitions may be applicable because a graph can be composed from basic
graphs in different ways (see Examples 2.2 and 3.1). So we are again forced to
choose and possibly to backtrack. To avoid this inefficient backtracking
procedure, we would like to identify a unique transition, if it exists, that
does not lead into a dead end, by inspecting only local information. To
motivate such a procedure, let us first consider the simplest non-trivial case
where $s$ has two outgoing transitions, say $\delta,\delta^{\prime}\in\Delta$
with $\delta\neq\delta^{\prime}$. Now assume that we can prove that every edge
read by a move using $\delta$ can never be read by any sequence of moves
starting with $\delta^{\prime}$. It is then clear that any move using
$\delta^{\prime}$ instead of $\delta$ must inevitably lead into a dead end,
and we know for sure that $\delta$ must be picked for continuing the
recognition process. Moreover, backtracking later and trying $\delta^{\prime}$
is meaningless because we already know that it will fail. It is thus crucial
to find out whether an edge read by a move using $\delta$ can also be read by
a sequence of moves starting with $\delta^{\prime}$. This is discussed next.

Again consider the situation where recognition has reached configuration
$(s,G)$, and two transitions $\delta,\delta^{\prime}\in\Delta$,
$\delta\neq\delta^{\prime}$, can be used for two competing moves

$\displaystyle(s,G)$
$\displaystyle\mathrel{\Vdash}_{\delta}(s^{\prime},G^{\prime})$ (1)
$\displaystyle(s,G)$
$\displaystyle\mathrel{\Vdash}_{\delta^{\prime}}(s^{\prime\prime},G^{\prime\prime})$
(2)

with $\delta=(s,a^{\varphi}_{\varrho},s^{\prime})$,
$\delta^{\prime}=(s,b^{\varphi^{\prime}}_{\varrho^{\prime}},s^{\prime\prime})$,
$G=G_{\delta}\mathop{\odot}G^{\prime}=G_{\delta^{\prime}}\mathop{\odot}G^{\prime\prime}$
for two graphs $G_{\delta}$ and $G_{\delta^{\prime}}$ with
$\bar{G}_{\delta}=\\{e\\}$, $\bar{G}_{\delta^{\prime}}=\\{e^{\prime}\\}$,
$G_{\delta}\cong\left\llbracket a^{\varphi}_{\varrho}\right\rrbracket$, and
$G_{\delta^{\prime}}\cong\left\llbracket
b^{\varphi^{\prime}}_{\varrho^{\prime}}\right\rrbracket$. The sequences
$\varphi$ and $\varphi^{\prime}$ specify how $e$ and $e^{\prime}$ must be
connected to front nodes of $G$ such that (1) and (2) are a valid moves,
respectively. To be more precise, let
$\xi,\xi^{\prime}\colon[\mathit{rank}(a)]\rightharpoonup[\mathit{rank}(s)]$ be
partial functions defined by

$\displaystyle\xi$
$\displaystyle=\\{(k,i)\in[\mathit{rank}(a)]\times[\mathit{rank}(s)]\mid
k=\varphi(i)\\}.$ (3) $\displaystyle\xi^{\prime}$
$\displaystyle=\\{(k,i)\in[\mathit{rank}(b)]\times[\mathit{rank}(s)]\mid
k=\varphi^{\prime}(i)\\}.$ (4)

Once more, we use the notation $\varphi(i)$ to access the $i$-th number within
the sequence $\varphi$. Thus, $\xi$ and $\xi^{\prime}$ assign the index of a
front node (in the sequence of all front nodes of $G$) to its index in the
sequence of all nodes attached to $e$ or $e^{\prime}$, respectively. If a node
is attached to $e$ or $e^{\prime}$ as its $k$-th node, but is not a front node
of $G$, $\xi(k)$ or $\xi^{\prime}(k)$ are undefined, respectively.

We now assume that $e$ is also read in the competing move (2) or a subsequent
move. If $e$ is read in (2), we have $e=e^{\prime}$ as well as $a=b$, and
$\xi=\xi^{\prime}$ follows.

If $e\neq e^{\prime}$, $e$ must be read later, that is, there must be a
sequence of moves

$\displaystyle(s^{\prime\prime},G^{\prime\prime})\mathrel{\Vdash}_{\mathfrak{A}_{\mathrm{d}}}^{\ast}(q,H)\mathrel{\Vdash}_{\delta^{\prime\prime}}(q^{\prime},H^{\prime})$
(5)

with
$\delta^{\prime\prime}=(q,a^{\varphi^{\prime\prime}}_{\varrho^{\prime\prime}},q^{\prime})$,
$H=H_{\delta^{\prime\prime}}\mathop{\odot}H^{\prime}$, and
$\bar{H}_{\delta^{\prime\prime}}=\\{e\\}$, and
$H_{\delta^{\prime\prime}}\cong\left\llbracket
a^{\varphi^{\prime\prime}}_{\varrho^{\prime\prime}}\right\rrbracket$.

Some front nodes of $G$ may also be front nodes of $H$ in (5). Let us indicate
this situation by a partial function
$\mu\colon[\mathit{rank}(s)]\rightharpoonup[\mathit{rank}(q)]$ defined by

$\mu=\\{(i,j)\in[\mathit{rank}(s)]\times[\mathit{rank}(q)]\mid\mathit{front}_{G}(i)=\mathit{front}_{H}(j)\\}$
(6)

Consequently, $\\{\mathit{front}_{G}(i)\mid i\in\mathit{dom}(\mu)\\}$ is the
subset of those front nodes of $G$ that are also front nodes of $H$. Similar
to $\xi$ and $\xi^{\prime}$, let us define the partial function
$\xi^{\prime\prime}\colon[\mathit{rank}(a)]\rightharpoonup[\mathit{rank}(s)]$
by

$\displaystyle\xi^{\prime\prime}$
$\displaystyle=\\{(k,i)\in[\mathit{rank}(a)]\times\mathit{dom}(\mu)\mid
k=\varphi^{\prime\prime}(\mu(i))\\}.$ (7)

Function $\mu$ is used to refer to front nodes of $G$ instead of front nodes
of $H$.

We now show that we have $\xi=\xi^{\prime\prime}$, similar to the case
$e=e^{\prime}$. To see this, consider any node $v$ attached to $e$, that is,
there is $k\in[\mathit{rank}(a)]$ such that $v=\mathit{att}_{G}(e,k)$.

  * •

If $v$ is not a front node of $G$, $k\notin[\varphi]$ follows from
$G_{\delta}\cong\left\llbracket a^{\varphi}_{\varrho}\right\rrbracket$, and
thus $k\notin\mathit{dom}(\xi)$. Now assume that
$k\in\mathit{dom}(\xi^{\prime\prime})$ and, hence,
$k=\varphi^{\prime\prime}(j)$ as well as $j=\mu(i)$ for some
$i\in[\mathit{rank}(s)]$ and $j\in[\mathit{rank}(q)]$. This implies
$\mathit{front}_{G}(i)=\mathit{front}_{H}(j)=\mathit{att}_{G}(e,k)=v$ in
contradiction to $v\notin[\mathit{front}_{G}]$. Hence,
$k\notin\mathit{dom}(\xi^{\prime\prime})$ as well.

  * •

If $v$ is a front node of $G$, there is an index $i\in[\mathit{rank}(s)]$ such
that $v=\mathit{front}_{G}(i)$ and $k=\varphi(i)$, because of
$G_{\delta}\cong\left\llbracket a^{\varphi}_{\varrho}\right\rrbracket$.
Consequently, $k\in\mathit{dom}(\xi)$ and $i=\xi(k)$. When $e$ is read in the
last move (using $\delta^{\prime\prime}$) in (5), it must also be a front node
of $H$ (otherwise, $H$ could not contain $v$ as a node because moves cannot
turn front nodes into non-front nodes). Hence, $i\in\mathit{dom}(\mu)$ and
$v=\mathit{front}_{H}(\mu(i))$. $H_{\delta^{\prime\prime}}\cong\left\llbracket
a^{\varphi^{\prime\prime}}_{\varrho^{\prime\prime}}\right\rrbracket$ also
implies $k=\varphi^{\prime\prime}(\mu(i))$, and thus
$k\in\mathit{dom}(\xi^{\prime\prime})$ as well as $i=\xi^{\prime\prime}(k)$.

Note that the definition of $\xi^{\prime\prime}$ in fact subsumes the
definition of $\xi^{\prime}$ when using the identity on $[\mathit{rank}(s)]$
as $\mu$. Suppose we could compute the set $\Xi(\delta^{\prime},a)$ of all
functions $\xi^{\prime\prime}$ defined as in (7) for any graph $G$ where $\mu$
represents any move sequence starting with $\delta^{\prime}$ applied to $G$
and finally reading an $a$-labelled edge (that is, exactly the situation as in
(2) and (5)). Then we can summarize the discussion above as follows: If $e$
can be read also in move (2) or later in (5), then
$\xi\in\Xi(\delta^{\prime},a)$. Since $\xi$ and $\Xi(a)$ are independent of
the specific choice of $G$ and $e$, we can state the following observation:

######  Observation 4.9.

Let $\delta,\delta^{\prime}\in\Delta$, $\xi$, and $\Xi(\delta^{\prime},a)$
defined as described above, $\xi\notin\Xi(\delta^{\prime},a)$, and
$G\in\mathcal{G}_{\Sigma}$ any graph such that $\delta$ can be applied to $G$.
Then $\delta^{\prime}$ must not be tried for a move because it either cannot
be applied to $G$, or its application leads inevitably into a dead end
eventually.

In fact, $\Xi(\delta^{\prime},a)$ can be computed in a rather straightforward
way using Algorithm 2. To simplify things, we use the notation
$\Delta_{q}=\\{\delta\in\Delta\mid\exists a\in\Theta,q^{\prime}\in
Q:\delta=(q,a,q^{\prime})\\}$ for indicating the set of transitions leaving a
state $q$. Let us further define

$\displaystyle\mathit{follow}(\delta)=\\{(a,\xi)\mid\xi\in\Xi(\delta,a)\\}.$
(8)

The following lemma states that Algorithm 2 computes
$\mathit{follow}(\delta)$.

Input : Finite automaton $\mathfrak{A}_{\mathrm{d}}=(\Theta,Q,\Delta,q_{0},F)$
produced by Algorithm 1 and a transition $\delta_{0}\in\Delta$.

Output : Follow set $\mathit{follow}$.

1 let $\delta_{0}\in\Delta_{s}$

2 $\mathit{frontier}\leftarrow\\{(\delta_{0},\nu)\\}$ where $\nu=\\{(i,i)\mid
i\in[\mathit{rank}(s)]\\}$

3 $\mathit{done}\leftarrow\varnothing$, $\mathit{follow}\leftarrow\varnothing$

4 while  _$\mathit{frontier}\neq\varnothing$_ do

5 select and remove any $(\delta,\mu)$ from $\mathit{frontier}$

6 add $(\delta,\mu)$ to $\mathit{done}$

7 let $\delta=(q,\alpha,q^{\prime})$

8 if  _$\alpha\notin\mathcal{B}$_ then

9 let $\alpha=a^{\varphi}_{\varrho}$

10 $\xi=\\{(i,j)\in[\mathit{rank}(a)]\times\mathit{dom}(\mu)\mid
i=\varphi(\mu(j))\\}$

11 add $(a,\xi)$ to $\mathit{follow}$

12
$\mu^{\prime}\leftarrow\\{(i,j)\in\mathit{dom}(\mu)\times[\mathit{rank}(q^{\prime})]\mid\varphi(\mu(i))=\varrho(j)\\}$

13 foreach  _$\delta^{\prime}\in\Delta_{q^{\prime}}$ such that
$(\delta^{\prime},\mu^{\prime})\notin\mathit{done}$_ do

14 add $(\delta^{\prime},\mu^{\prime})$ to $\mathit{frontier}$

15

16

Algorithm 2 Determining $\mathit{follow}(\delta_{0})$.

######  Lemma 4.10.

Let $\Sigma$ be a ranked alphabet, $\Theta$ a finite set of canonical graph
symbols for $\Sigma$, $\mathfrak{A}_{\mathrm{d}}=(\Theta,Q,\Delta,q_{0},F)$ a
finite automaton produced by Algorithm 1, and $\delta_{0}\in\Delta$ a
transition. Called with $\mathfrak{A}_{\mathrm{d}}$ and $\delta_{0}$,
Algorithm 2 returns $\mathit{follow}(\delta_{0})$ for
$\mathfrak{A}_{\mathrm{d}}$.

######  Proof Sketch.

Consider any $\mathfrak{A}_{\mathrm{d}}$ and $\delta_{0}$ as in the lemma. We
first show that Algorithm 2 terminates. To see this, first note that
$\mathit{dom}(\mu^{\prime})\subseteq\mathit{dom}(\mu)$ and
$\mu^{\prime}(x)\in[\mathit{rank}(q^{\prime})]$ for each
$x\in\mathit{dom}(\mu^{\prime})$ of function $\mu^{\prime}$ defined in Line 2,
and thus $\mathit{dom}(\mu^{\prime})\subseteq[\mathit{rank}(s)]$ for every
pair $(\delta^{\prime},\mu^{\prime})$ ever added to $\mathit{frontier}$ in
Line 2. Consequently, only finitely many pairs $(\delta,\mu)$ can be added to
$\mathit{frontier}$ and $\mathit{done}$. And because no pair is added to
$\mathit{frontier}$ again after it has been selected in Line 2 (and adding it
to $\mathit{done}$ in Line 2), Algorithm 2 terminates.

Now consider any $a\in\Sigma$, $\xi\in\Xi(\delta_{0},a)$ as for Observation
4.9, and any graph $G\in\mathbb{G}_{\Sigma}$. Consequently, there is a move
sequence starting with $\delta_{0}$ and finally reading an $a$-labeled edge
using some transition $\delta$ such that $\xi$ is defined like $\xi^{\prime}$
or $\xi^{\prime\prime}$ in (4) and (7), respectively, and using an appropriate
partial function $\mu$. By induction on the move sequence, one can show that
$\mathit{frontier}$ eventually will contain $(\delta,\mu)$. Consequently,
$(a,\xi)$ is added to $\mathit{follow}$ in Line 2, that is, $(a,\xi)$ is
contained in the result of Algorithm 2 as required.

For the other direction, consider any pair $(a,\xi)$ in the result of
Algorithm 2. By induction on the number of iterations of the while-loop
starting at Line 2, one can show that the set $\mathit{done}$ only contains
pairs $(\delta,\mu)$ such that there exists a move sequence starting with
$\delta_{0}$ and ending with $\delta$ so that $\mu$ is exactly as in (6).
Since $(a,\xi)\in\mathit{follow}$, it must have been added to
$\mathit{follow}$ in Line 2 at some point after selecting $(\delta,\mu)$ in
Line 2. Using (4) and (7), one can show that $\xi\in\Xi(\delta_{0},a)$ as
required.∎

We now use Observation 4.9 for identifying the unique transition (if it
exists) that does not lead into a dead end, provided that
$\mathfrak{A}_{\mathrm{d}}$ satisfies certain conditions. To this end, let us
define

$\displaystyle\mathit{next}(\delta)=(a,\xi)$ (9)

for each transition $\delta=(s,a^{\varphi}_{\varrho},s^{\prime})\in\Delta$
where $\xi$ is defined as in (3). Moreover, let
$\prec_{q}\;\subseteq\Delta_{q}\times\Delta_{q}$ be such that

$\displaystyle\delta\prec_{q}\delta^{\prime}\quad\text{if}\quad\mathit{next}(\delta^{\prime})\in\mathit{follow}(\delta)$
(10)

for each $q\in Q$. According to Observation 4.9,
$\delta^{\prime}\not\prec_{q}\delta$ then indicates that $\delta^{\prime}$ may
only be tried if $\delta$ cannot be applied.

Consider any state $q\in Q$. If $\prec_{q}^{+}$ is irreflexive, one can extend
$\prec_{q}$, by topological sorting, to a strict total order
$\sqsubset_{q}\;\subseteq\Delta_{q}\times\Delta_{q}$ such that
$\prec_{q}\;\subseteq\;\sqsubset_{q}$. Such an order $\sqsubset_{q}$ has the
following nice property with respect to Observation 4.9:

######  Lemma 4.11.

Let $q\in Q$, $\sqsubset_{q}\;\subseteq\Delta_{q}\times\Delta_{q}$ a strict
total order such that $\prec_{q}\;\subseteq\;\sqsubset_{q}$, and
$\delta,\delta^{\prime}\in\Delta_{q}$. Then
$\delta\sqsubset_{q}\delta^{\prime}$ implies
$\mathit{next}(\delta)\notin\mathit{follow}(\delta^{\prime})$.

###### Proof.

Consider any $q\in Q$ and $\delta,\delta^{\prime}\in\Delta_{q}$ with
$\delta\sqsubset_{q}\delta^{\prime}$. Then
$\mathit{next}(\delta)\in\mathit{follow}(\delta^{\prime})$ would imply
$\delta^{\prime}\prec_{q}\delta$ and thus
$\delta^{\prime}\sqsubset_{q}\delta$, contradicting the irreflexivity of
$\sqsubset_{q}$. ∎

Such a total strict order $\sqsubset_{q}$ only exists if $\prec_{q}^{+}$ is
irreflexive, which motivates the following:

######  Definition 4.12 (Transition Selection Property).

A DFA $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ has the _transition selection_
(_TS_) _property_ if $\prec_{q}^{+}$ as defined in (10) is irreflexive for
each state $q\in Q$.

An immediate consequence of Lemma 4.11 is the following:

######  Lemma 4.13.

For every DFA $\mathfrak{A}$ with the TS property, there is a constant time
procedure which, given a configuration of $\mathfrak{A}$, selects the unique
transition that allows to continue the recognition process without running
into a dead end, provided that such a transition exists.

###### Proof.

Assume that a configuration with state $q$ has been reached during
recognition. There exists an order $\sqsubset_{q}$ as in Lemma 4.11 because of
the TS property. Now try all outgoing transitions of $q$ in ascending order of
$\sqsubset_{q}$ and pick the first one, say $\delta$, that can be applied.
Then $\delta\sqsubset_{q}\delta^{\prime}$ holds for every outgoing transition
$\delta^{\prime}$ that has not yet been tried, and thus
$\mathit{next}(\delta)\notin\mathit{follow}(\delta^{\prime})$ by Lemma 4.11,
that is, $\delta^{\prime}$ must not be tried by Observation 4.9 because
$\delta$ can be applied.

The relation $\sqsubset_{q}$ depends only on $\mathfrak{A}$ and $q$, and can
thus be precomputed for every state $q$. Checking whether a given transition
applies takes constant time, because all that is required is to test whether
an edge with the relevant label is attached to the front nodes of the graph as
determined by the symbol to be read by the transition. Using appropriate data
structures, this can straightforwardly be implemented to run in constant time.
∎

######  Example 4.4.

Only state $S_{1}$ of the DFA $\mathfrak{S}^{\prime}$ shown in Figure 5 has
two outgoing transitions, $\delta_{2}$ and $\delta_{3}$. We obtain

$\displaystyle\mathit{next}(\delta_{2})$ $\displaystyle=(a,\\{(1,1)\\})$
$\displaystyle\mathit{follow}(\delta_{2})$
$\displaystyle=\\{(a,\\{(1,1)\\}),(b,\\{(1,1)\\})\\}$
$\displaystyle\mathit{next}(\delta_{3})$ $\displaystyle=(b,\\{(1,1)\\})$
$\displaystyle\mathit{follow}(\delta_{3})$
$\displaystyle=\\{(b,\\{(1,1)\\})\\}$

by applying (9) with (3) and using Algorithm 2, that is,
$\delta_{2}\prec_{S_{1}}\delta_{3}$ and
$\delta_{3}\not\prec_{S_{1}}\delta_{2}$, that is, $\mathfrak{S}^{\prime}$ has
the TS property. We can thus choose $\delta_{2}\sqsubset_{S_{1}}\delta_{3}$,
that is, one must try $\delta_{2}$ first when one has reached $S_{1}$, and
$\delta_{3}$ only if $\delta_{2}$ is not applicable, that is, if there is no
remaining outgoing edge with label $a$.

###  4.4 Free Edge Choice

Unfortunately, the transition selection property does not necessarily prevent
the recognition process from running into dead ends, even for valid graphs.
This is the case if one has the choice between different edges to be read by a
selected transition, but not all of them are equally suited. This is
demonstrated in the following example:

######  Example 4.5.

$S_{0}$$S_{1}$$S_{2}$$S_{f}$$a^{1}_{12}$$\delta_{1}$$b^{31}_{3}$$\delta_{2}$$c^{31}_{2}$$\delta_{3}$$\varepsilon^{(1)}$$\delta_{4}$

$v$$w$$x$$y$$z$$b$$a$$a$$c$

$v$$w$$x$$y$$z$$b$$a$$c$

Figure 8: Finite automaton $\mathfrak{F}$ and two graphs used in Example 4.5.

Let $a$, $b$, and $c$ be symbols of rank 2. The DFA $\mathfrak{F}$ shown in
Figure 8 always allows to select a unique transition: $\delta_{1}$ in state
$S_{0}$, $\delta_{2}$ in $S_{1}$ if the second front interface node has an
outgoing $b$-edge, and $\delta_{3}$ if it has an outgoing $c$-edge. The left
graph in Figure 8 can thus be recognized by first reading the edge from $x$ to
$v$ in state $S_{0}$ and then following the uniquely determined moves.

However, the recognition process will run into a dead end if it reads the edge
from $x$ to $y$ first. This move then yields a configuration
$(S_{1},G^{\prime})$ where $G^{\prime}$ is the right graph in Figure 8. The
second front interface node ($y$) has an outgoing $c$-edge, but no $b$-edge,
that is, $\delta_{3}$ is selected. This transition tries to find a composition
$G^{\prime}=C\mathop{\odot}G^{\prime\prime}$ with $C\cong\left\llbracket
c^{31}_{2}\right\rrbracket$, that is, $\mathit{front}_{C}=xy$,
$\mathit{rear}_{C}=z$, and thus $x\notin\dot{G}^{\prime\prime}$, which would
leave the edge from $x$ to $v$ dangling. Hence, $\delta_{3}$ cannot be applied
which leaves the recognition process stuck in a dead end.∎

Such a situation cannot happen if every edge that can be chosen to be read
next allows to continue the recognition process until an accepting
configuration is reached, or none of them does. We say that the next edge can
be freely chosen:

######  Definition 4.14 (Free Edge Choice Property).

A finite automaton $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ has the _free edge
choice_ (_FEC_) _property_ if
$(q^{\prime},H^{\prime})\in\mathcal{C}_{\mathfrak{A}}$ implies
$(q^{\prime},H^{\prime\prime})\in\mathcal{C}_{\mathfrak{A}}$ for all move
sequences
$(q_{0},G)\mathrel{\Vdash}_{\mathfrak{A}}^{\ast}(q,H)\mathrel{\Vdash}_{\delta}(q^{\prime},H^{\prime})$
and $(q,H)\mathrel{\Vdash}_{\delta}(q^{\prime},H^{\prime\prime})$ where
$\delta\in\Delta$.333Recall that $\mathcal{C}_{\mathfrak{A}}$ is the set of
all acceptable graph configurations of $\mathfrak{A}$, that is, those
configurations from where an accepting configuration can be reached (see
Definition 3.3).

By the discussion above, the recognition process using an automaton with the
TS property and the FEC property will never run into a dead end when applied
to a valid graph. It remains to show how the FEC property can be checked for a
given automaton. We present a sufficient condition that is easy to test. Thus,
an automaton is guaranteed to have the FEC property if it passes the test, but
the converse is not necessarily true.

Consider a situation during the recognition of a valid graph when a transition
has been selected for the next move, and there are several edges one can
choose from. All the edges that are not being chosen now must be read later
during the recognition process. This is only possible for certain transitions.
Let us call these transitions _deferrable_ because one edge can be read now
whereas reading of the others is deferred:

A transition $\delta\in\Delta$ is called _deferrable_ if and only if there are
move sequences

$\displaystyle(q,G)\mathrel{\Vdash}_{\delta}(q^{\prime},G^{\prime})$ (11) and
$\displaystyle(q,G)\mathrel{\Vdash}_{\delta}(q^{\prime},G^{\prime\prime})\mathrel{\Vdash}_{\mathfrak{A}}^{\ast}(s,H)\mathrel{\Vdash}_{\mathfrak{A}}(s^{\prime},H^{\prime})$
(12)

such that the edge read in (11) and the one read in the last move of (12) are
the same, that is
$\bar{G}^{\prime}\setminus\bar{G}=\bar{H}^{\prime}\setminus\bar{H}$.

One can easily check with an algorithm similar to Algorithm 2 whether a
transition is deferrable. With this information, one can then check whether
$\mathfrak{A}$ has the FEC property:

######  Lemma 4.15.

A finite automaton $\mathfrak{A}$ has the free edge choice property if
$[\varrho]\subseteq[\varphi]$ holds for every transition
$(q,a^{\varphi}_{\varrho},q^{\prime})$ of $\mathfrak{A}$ that is deferrable.

###### Proof.

Consider a finite automaton $\mathfrak{A}=(\Theta,Q,\Delta,q_{0},F)$ that
satisfies the condition in the lemma. Let us assume that $\mathfrak{A}$ does
not have the free edge choice property, that is, there are move sequences
$(q_{0},G)\mathrel{\Vdash}_{\mathfrak{A}}^{\ast}(q,H)\mathrel{\Vdash}_{\delta}(q^{\prime},H^{\prime})\in\mathcal{C}_{\mathfrak{A}}$
and
$(q,H)\mathrel{\Vdash}_{\delta}(q^{\prime},H^{\prime\prime})\notin\mathcal{C}_{\mathfrak{A}}$.
The two moves using $\delta$ must have read two different edges, say $e$ and
$e^{\prime}$, that is,
$H=F\mathop{\odot}H^{\prime}=F^{\prime}\mathop{\odot}H^{\prime\prime}$,
$\bar{F}=\\{e\\}$, and $\bar{F}^{\prime}=\\{e^{\prime}\\}$. $H^{\prime}$ then
still contains $e^{\prime}$, which is read later, because
$(q^{\prime},H^{\prime})\in\mathcal{C}_{\mathfrak{A}}$. Consequently, there is
a move sequence
$(q^{\prime},H^{\prime})\mathrel{\Vdash}_{\mathfrak{A}}^{\ast}(s,I)\mathrel{\Vdash}_{\mathfrak{A}}(s^{\prime},I^{\prime})\in\mathcal{C}_{\mathfrak{A}}$
such that $\bar{I}\setminus\bar{I}^{\prime}=\\{e^{\prime}\\}$, that is,
$\delta$ is deferrable. Now let $\delta=(q,a^{\varphi}_{\varrho},q^{\prime})$.
We have $a=\mathit{lab}_{G}(e)=\mathit{lab}_{G}(e^{\prime})$ since $e$ and
$e^{\prime}$ can both be read by $\delta$. And we have
$[\varrho]\subseteq[\varphi]$ since $\delta$ is deferrable, and $\mathfrak{A}$
satisfies the condition in the lemma. Note that
$\mathit{front}_{H}=\mathit{front}_{F}=\mathit{front}_{F^{\prime}}$. Thus
$[\varrho]\subseteq[\varphi]$ implies
$\mathit{rear}_{F}=\mathit{rear}_{F^{\prime}}=\mathit{front}_{H^{\prime}}=\mathit{front}_{H^{\prime\prime}}$.
Consequently, all nodes of $H$ that are attached to $e$ or $e^{\prime}$, but
that are not in $\mathit{front}_{H}$, cannot be attached to any other edge,
and thus $H^{\prime}\cong H^{\prime\prime}$, where the isomorphism maps $e$ to
$e^{\prime}$ (and vice versa). Then
$(q^{\prime},H^{\prime\prime})\in\mathcal{C}_{\mathfrak{A}}$ follows from
$(q^{\prime},H^{\prime})\in\mathcal{C}_{\mathfrak{A}}$, contradicting the
assumption. $\mathfrak{A}$ hence has the free edge property. ∎

######  Example 4.6.

Transition $\delta_{1}$ is the only deferrable transition of automaton
$\mathfrak{F}$ in Figure 8, but it violates the condition of Lemma 4.15 as it
reads $a^{1}_{12}$, and $[\varrho]=\\{1,2\\}\not\subseteq\\{1\\}=[\varphi]$.
Consequently, $\mathfrak{F}$ does not pass the FEC test, which leaves the
question open whether $\mathfrak{F}$ has the FEC property or not. In fact, we
have already seen in Example 4.5 that $\mathfrak{F}$ does not have the FEC
property.

The automaton $\mathfrak{S}^{\prime}$ in Figure 5, however, has the FEC
property according to Lemma 4.15 since $\delta_{2}$ is its only deferrable
transition, and $[\varrho]=\\{1\\}\subseteq\\{1\\}=[\varphi]$ for the graph
symbol $a^{1}_{1}$ read by $\delta_{2}$. Since $\mathfrak{S}^{\prime}$ also
has the TS property (see Example 4.4), one can use $\mathfrak{S}^{\prime}$ for
recognizing star graphs without any backtracking.

###  4.5 Results

The following theorem summarizes the findings of this paper.

######  Theorem 4.16.

  1. 1.

Every finite automaton over the canonical alphabet can effectively be turned
into a DFA.444As usual, and unavoidably, the powerset construction can cause
an exponential blow-up in the size of the automaton.

  2. 2.

Given a DFA $\mathfrak{A}$ (of the type produced by Algorithm 1), it can be
decided in polynomial time (in the number of transitions of $\mathfrak{A}$)
whether $\mathfrak{A}$ has the TS and the FEC property.

  3. 3.

If $\mathfrak{A}$ has the TS and the FEC property, the membership problem for
${\mathcal{L}}(\mathfrak{A})$ can be decided in linear time.

###### Proof.

The first statement follows from Theorem 4.8 and the previously mentioned fact
that ambiguous automata can be made unambiguous. Deciding the TS property
requires polynomial time because Algorithm 2 and topological sorting must be
used for checking irreflexivity of $\prec_{q}^{+}$ for every state $q$ of
$\mathfrak{A}$. The second statement then follows from Lemma 4.15 and the fact
that it is decidable in polynomial time whether a transition is deferrable
(see above). Finally, to decide whether a graph belongs to
${\mathcal{L}}(\mathfrak{A})$, we can repeatedly apply transitions using Lemma
4.13. ∎

The concepts described in this paper have been realized in a graphical tool.
It reads in a finite automaton over the canonical alphabet, or creates it from
a regular expression in the obvious way, turns it into a DFA, and uses it for
recognizing input graphs if the DFA has the TS and the FEC property. Figure 9
shows a screenshot with an input graph in the top-left window, and the DFA in
the top-right window after the DFA has recognized the input graph. The bottom
window shows how the input graph has been composed from basic graphs such that
it has been accepted by the DFA.

Figure 9: Screenshot of a tool realizing efficient graph recognition based on
finite automata.

Table 1 shows some example graph languages that can be specified and
efficiently recognized by finite automata: _Stars_ is the language of stars
used in this paper (Example 3.1), _Wheels_ contains wheel graphs introduced in
[24, p. 92], _Palindromes_ contains all palindromes over $\\{a,b\\}$, and
$a^{n}b^{n}c^{n}$ the language $\\{a^{n}b^{n}c^{n}\mid n>0\\}$ as string
graphs [24, Ex. 2.4]. Table 1 shows the type of the contained graphs, that is,
the size of their front and rear interfaces, and the size of their DFA in
terms of the number of states and transitions. Moreover, _max. #nodes_ shows
the number of nodes of the largest atom used in the DFA. Each of the automata
has the TS and FEC property.

Table 1: Example graph languages and their finite automata. Language | Type | #states | #transitions | max. #nodes | TS | FEC
---|---|---|---|---|---|---
Stars | $(1,1)$ | 4 | 4 | 2 | $\checked$ | $\checked$
Wheels | $(1,0)$ | 7 | 7 | 4 | $\checked$ | $\checked$
Palindromes | $(2,0)$ | 5 | 7 | 3 | $\checked$ | $\checked$
$a^{n}b^{n}c^{n}$ | $(2,0)$ | 9 | 10 | 4 | $\checked$ | $\checked$

Figure 9 shows the DFA for wheels and a wheel with six spokes (s-edges for
spokes and t-edges for the tread of the wheel). The front and rear interfaces
of the wheel are empty. As shown in the bottom window, the left-most atom
refers to the t-edge from n1 to n2, and recognition of the wheel has started
with this part of the tread of the wheel. Recognition could have started with
any of the t-edges because the DFA has the FEC property. However, the FEC test
fails for this DFA because of the first transition from Q0 to Q1 with label
t^$\varepsilon$_12, which represents $t^{\varepsilon}_{12}$. This transition
is deferrable, yet $\\{1,2\\}\not\subseteq\varnothing$. Hence, _Wheels_ is an
example where the simple FEC test fails although the automaton does have the
FEC property.

##  5 Conclusions

In this paper we have defined finite automata for graph recognition, devised a
modified powerset construction to make them deterministic, and stated two
criteria (transition selection and free edge choice) under which these
automata work without backtracking.

This paper leaves some questions open. Do (nondeterministic) finite graph
automata recognize NP-complete languages, which exist for (context-free)
hyperedge replacement grammars? How do the languages accepted by finite graph
automata relate to those definable with the “regular” graph grammars of Gilroy
_et al._ [21], which have an efficient parsing algorithm (not defined with
automata) that also requires free edge choice? (Probably these language
classes are incomparable.)

We intend to continue our work in several directions. First, it is easy to
define graph expressions defining graph languages by composition, Kleene star,
and union. These expressions could be used in the nested graph conditions of
Habel and Pennemann [25, 31] to specify global graph properties [20], and
check them with automata. Second, we could consider borrowed nodes in graph
expressions and graph automata that can be contracted with other nodes in a
graph [17]. Then these mechanisms allow to define graphs of unbounded
treewidth.

#### Acknowledgments.

We are very grateful to the anonymous reviewers for their helpful comments and
suggestions, which have helped to improve the quality of this paper.

## References

  * [1]
  * [2] Ĳ.J. Aalbersberg, Andrzej Ehrenfeucht & Grzegorz Rozenberg (1986): _On the Membership Problem for Regular DNLC Grammars_.  Discrete Applied Mathematics 13, pp. 79–85, 10.1016/0166-218X(86)90070-3.
  * [3] Michael A. Arbib & Yehoshafat Give’on (1968): _Algebra Automata I: Parallel Programming as a Prolegomena to the Categorical Approach_.  Information and Control 12(4), pp. 331–345, 10.1016/S0019-9958(68)90374-4.
  * [4] Christoph Blume, H.J. Sander Bruggink, Martin Friedrich & Barbara König (2013): _Treewidth, Pathwidth and Cospan Decompositions with Applications to Graph-Accepting Tree Automata_.  Journal of Visual Languages & Computing 24(3), pp. 192–206, 10.1016/j.jvlc.2012.10.002.
  * [5] Symeon Bozapalidis & Antonios Kalampakas (2006): _Recognizability of graph and pattern languages_.  Acta Informatica 42(8-9), pp. 553–581, 10.1007/s00236-006-0006-z.
  * [6] Symeon Bozapalidis & Antonios Kalampakas (2008): _Graph automata_.  Theoretical Computer Science 393(1-3), pp. 147–165, 10.1016/j.tcs.2007.11.022.
  * [7] Franz-Josef Brandenburg & Konstantin Skodinis (2005): _Finite graph automata for linear and boundary graph languages_.  Theoretical Computer Science 332(1-3), pp. 199–232, 10.1016/j.tcs.2004.09.040.
  * [8] H. J. Sander Bruggink & Barbara König (2018): _Recognizable languages of arrows and cospans_.  Math. Struct. Comput. Sci. 28(8), pp. 1290–1332, 10.1017/S096012951800018X.
  * [9] David Chiang, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, Bevan Jones & Kevin Knight (2013): _Parsing Graphs with Hyperedge Replacement Grammars_.  In: Proc. 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Association for Computational Linguistics, Sofia, Bulgaria, pp. 924–932.  Available at https://aclanthology.org/P13-1091.
  * [10] Bruno Courcelle (1990): _The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs_.  Information and Computation 85(1), pp. 12–75, 10.1016/0890-5401(90)90043-H.
  * [11] Frank Drewes (1993): _Recognising $k$–connected hypergraphs in cubic time_.  Theoretical Computer Science 109, pp. 83–122, 10.1016/0304-3975(93)90065-2.
  * [12] Frank Drewes, Berthold Hoffmann & Mark Minas (2015): _Predictive Top-Down Parsing for Hyperedge Replacement Grammars_.  In Francesco Parisi-Presicce & Bernhard Westfechtel, editors: Graph Transformation - 8th International Conf., ICGT 2015. Proceedings, LNCS 9151, Springer, pp. 19–34, 10.1007/978-3-319-21145-9_2.
  * [13] Frank Drewes, Berthold Hoffmann & Mark Minas (2017): _Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars_.  In Fabio Gadducci & Timo Kehrer, editors: Graph Transformation - 10th International Conf., ICGT 2017, Proceedings, LNCS 12741, Springer, pp. 106–122, 10.1007/978-3-319-61470-0_7.
  * [14] Frank Drewes, Berthold Hoffmann & Mark Minas (2019): _Extending Predictive Shift-Reduce Parsing to Contextual Hyperedge Replacement Grammars_.  In Esther Guerra & Fernando Orejas, editors: Graph Transformation - 12th International Conf., ICGT 2019, LNCS 11629, Springer, pp. 55–72, 10.1007/978-3-030-23611-3_4.
  * [15] Frank Drewes, Berthold Hoffmann & Mark Minas (2019): _Formalization and Correctness of Predictive Shift-Reduce Parsers for Graph Grammars based on Hyperedge Replacement_.  Journal on Logical and Algebraic Methods for Programming 104, pp. 303–341, 10.1016/j.jlamp.2018.12.006.
  * [16] Frank Drewes, Berthold Hoffmann & Mark Minas (2021): _Rule-Based Top-Down Parsing for Acyclic Contextual Hyperedge Replacement Grammars_.  In Fabio Gadducci & Timo Kehrer, editors: Graph Transformation - 14th International Conference, ICGT 2021, LNCS 12741, Springer, pp. 164–184, 10.1007/978-3-030-78946-6_9.
  * [17] Frank Drewes, Berthold Hoffmann & Mark Minas (2022): _Acyclic Contextual Hyperedge Replacement: Decidability of Acyclicity and Generative Power_.  In Nicolas Behr & Daniel Strüber, editors: Graph Transformation - 15th International Conference, ICGT 2022, LNCS 13349, Springer, pp. 3–19, 10.1007/978-3-031-09843-7_1.
  * [18] Joost Engelfriet & Jan Joris Vereijken (1997): _Context-Free Graph Grammars and Concatenation of Graphs_.  Acta Informatica 34(10), pp. 773–803, 10.1007/s002360050106.
  * [19] Fabio Gadducci & Reiko Heckel (1997): _An inductive view of graph transformation_.  In Francesco Parisi-Presicce, editor: Recent Trends in Algebraic Development Techniques, 12th International Workshop, WADT’97, LNCS 1376, Springer, pp. 223–237, 10.1007/3-540-64299-4_36.
  * [20] Haim Gaifman (1982): _On local and non-local properties_.  In J. Stern, editor: Proc. of the Herbrand Symposium, Logic Colloquium, Studies in Logic and the Foundations of Mathematics 105, North-Holland, pp. 105–135, 10.1016/S0049-237X(08)71879-2.
  * [21] Sorcha Gilroy, Adam Lopez & Sebastian Maneth (2017): _Parsing Graphs with Regular Graph Grammars_.  In: Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017), Association for Computational Linguistics, Vancouver, Canada, pp. 199–208, 10.18653/v1/S17-1024.
  * [22] Sorcha Gilroy, Adam Lopez, Sebastian Maneth & Pijus Simonaitis (2017): _(Re)introducing Regular Graph Languages_.  In Makoto Kanazawa, Philippe de Groote & Mehrnoosh Sadrzadeh, editors: Proceedings of the 15th Meeting on the Mathematics of Language, MOL 2017, London, UK, July 13-14, 2017, ACL, pp. 100–113, 10.18653/v1/w17-3410.
  * [23] Yehoshafat Give’on & Michael A. Arbib (1968): _Algebra Automata II: The Categorical Framework for Dynamic Analysis_.  Information and Control 12(4), pp. 346–370, 10.1016/S0019-9958(68)90381-1.
  * [24] Annegret Habel (1992): _Hyperedge Replacement: Grammars and Languages_.  LNCS 643, Springer, 10.1007/BFb0013875.
  * [25] Annegret Habel & Karl-Heinz Pennemann (2005): _Nested Constraints and Application Conditions for High-Level Structures_.  In H.-J. Kreowski et al., editors: Formal Methods in Software and System Modeling, LNCS 3393, Springer, pp. 293–308, 10.1007/978-3-540-31847-7_17.
  * [26] Berthold Hoffmann & Mark Minas (2017): _Generating Efficient Predictive Shift-Reduce Parsers for Hyperedge Replacement Grammars_.  In M. Seidl & S. Zschaler, editors: STAF 2017 Workshops, LNCS 10748, Springer, pp. 76–91, 10.1007/978-3-319-74730-9_7.
  * [27] Antonios Kalampakas (2011): _Graph Automata: The Algebraic Properties of Abelian Relational Graphoids_.  In Werner Kuich & George Rahonis, editors: Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement, LNCS 7020, Springer, pp. 168–182, 10.1007/978-3-642-24897-9_8.
  * [28] Michael Kaminski & Shlomit S. Pinter (1992): _Finite Automata on Directed Graphs_.  Journal of Computer and System Sciences 44(3), pp. 425–446, 10.1016/0022-0000(92)90012-8.
  * [29] Klaus-Jörn Lange & Emo Welzl (1987): _String Grammars with Disconnecting or a Basic Root of the Difficulty in Graph Grammar Parsing_.  Discrete Applied Mathematics 16, pp. 17–30, 10.1016/0166-218X(87)90051-5.
  * [30] Clemens Lautemann (1990): _The complexity of graph languages generated by hyperedge replacement_.  Acta Informatica 27, pp. 399–421, 10.1007/BF00289017.
  * [31] Karl-Heinz Pennemann (2009): _Development of Correct Graph Transformation Systems_.  Dissertation, Carl-von-Ossietzky-Universität Oldenburg.  Available at http://oops.uni-oldenburg.de/884/1/pendev09.pdf.
  * [32] Walter Vogler (1991): _Recognizing Edge Replacement Graph Languages in Cubic Time_.  In H. Ehrig, H.-J. Kreowski & G. Rozenberg, editors: Proc. Fourth Intl. Workshop on Graph Grammars and Their Application to Comp. Sci., LNCS 532, Springer, pp. 676–687, 10.1007/BFb0017421.
  * [33] Kurt-Ulrich Witt (1981): _Finite Graph-Acceptors and Regular Graph-Languages_.  Information and Control 50(3), pp. 242–258, 10.1016/S0019-9958(81)90351-X.