algorithms{1,2} modules

We describe the interface for the algorithms.

Both modules: algorithms1 and algorithms2 have the same interface and provide the algorithm for the same decision problems.

Additional we describe here the used forbidden pattern. These pattern is taken from _[Schm00].

Each forbidden pattern is defined as conjunction of constraints over an DFA \(\mathcal A = (Q, \Sigma, \delta, s_0, F)\). You should consider, that if an DFA \(\dea A\) satisfied a forbidden pattern iff. \(L(\dea A) \not in \mathbb C\). Forbidden can be shown graphical in an similiar way to transition diagrams.

Straubing-Therien

\[\newcommand\mathdef{{=_{\text{def}}}} \newcommand\lclass[1]{{\mathcal{#1}}} \newcommand\dea[1]{{\mathcal{#1}}} \newcommand\reg[1]{{\mathbf{#1}}}\]\[ \let\notmodels\nvDash\]\[ \DeclareMathOperator{\Pol}{Pol} \DeclareMathOperator{\BC}{BC} \DeclareMathOperator{\co}{co} \DeclareMathOperator{\BFS}{BFS} \DeclareMathOperator{\ZK}{ZK} \DeclareMathOperator{\sZK}{sZK}\]\[ \DeclareMathOperator{\first}{first} \DeclareMathOperator{\last}{last} \DeclareMathOperator{\append}{append}\]\[ \newcommand\FP{\ensuremath{\mathcal{FP}}\xspace}\]\[\begin{split}\begin{align} \mathbb{L}_{1/2} \mathdef & \quad \exists{ p,q \in Q} \colon \\ & \qquad \exists{ x,z,w \in \Sigma^* } \colon\\ & \qquad ~ \quad\, \hat \delta (q_0, x) = p\\ & \qquad ~ \wedge \hat \delta (p, w) = q \\ & \qquad ~ \wedge \hat \delta (p, z) = + \\ & \qquad ~ \wedge \hat \delta (q, z) = - \end{align}\end{split}\]

\[\begin{split}\begin{align} \mathbb{L}^1_{1} \mathdef & \quad \exists{ p,q \in Q} \colon \\ & \qquad \exists{ x,v,w,z \in \Sigma^* } \colon\\ & \qquad ~ \quad\, \hat \delta (q_0, x) = p \\ & \qquad ~ \wedge \hat \delta (p, w) = q \\ & \qquad ~ \wedge \hat \delta (q, v) = p \\ & \qquad ~ \wedge \hat \delta (p, z) \in F \nLeftrightarrow \hat \delta (q, z) \in F\\ \mathbb{L}^2_{1} \mathdef & \quad \exists{ p,q \in Q} \colon \\ & \qquad \exists{ x,v,w,z \in \Sigma^* } \colon\\ & \qquad ~ \quad\,\hat \delta (q_0, x) = p \\ & \qquad ~ \wedge \hat \delta (q, v) = s \\ & \qquad ~ \wedge \hat \delta (q, u) = p \\ \nonumber \\ & \qquad ~ \wedge \hat \delta (p, v) = r \\ & \qquad ~ \wedge \hat \delta (r, u) = p \\ \nonumber \\ & \qquad ~ \wedge \hat \delta (s, u) = t \\ & \qquad ~ \wedge \hat \delta (t, v) = s \\ \nonumber \\ & \qquad ~ \wedge \hat \delta (p, z) \in F \nLeftrightarrow \hat \delta (t, z) \in F \end{align}\end{split}\]

\[\begin{split}\begin{align} \mathbb B_1 \mathdef & \quad \exists{ p,q \in Q} \colon \\ & \qquad \exists{ x,z \in \Sigma^* } \colon\\ & \qquad \exists{ v,w \in \Sigma^+ } \colon\\ & \qquad ~ \quad\, \hat \delta (q_0, x) = p \\ & \qquad ~ \wedge \hat \delta (p, w) = q \\ & \qquad ~ \wedge \hat \delta (p, z) = + \\ & \qquad ~ \wedge \hat \delta (q, z) = - \\ & \qquad ~ \wedge \hat \delta (q, v) = q \\ & \qquad ~ \wedge \hat \delta (p, v) = p \\ & \qquad ~ \wedge \alpha(w) \subseteq \alpha(v) \end{align}\end{split}\]

Dot-Depth Hierarchy

\[\begin{split}\begin{align} \mathbb{B}_{1/2} \mathdef & \quad \exists{ p,q \in Q} \colon \\ & \qquad \exists{ x,z \in \Sigma^* } \colon\\ & \qquad \exists{ v,w \in \Sigma^+ } \colon\\ & \qquad ~ \quad\,\hat \delta (q_0, x) = p \\ & \qquad ~ \wedge \hat \delta (p, w) = q \\ & \qquad ~ \wedge \hat \delta (p, z) = + \\ & \qquad ~ \wedge \hat \delta (q, z) = - \\ & \qquad ~ \wedge \hat \delta (p, v) = p \\ & \qquad ~ \wedge \hat \delta (q, v) = q \end{align}\end{split}\]

\[\begin{split}\begin{align} \mathbb{B}_1 \mathdef & \quad \exists{ p,q \in Q} \colon \\ & \qquad \exists{ x,y,y',u,v,z \in \Sigma^* } \colon\\ & \qquad \exists{ w,w' \in \Sigma^+ } \colon\\ & \qquad ~ \quad\,\hat \delta (q_0, x) = q_1\\ & \qquad ~ \wedge \hat \delta (q_1, y) = q_2 & & \wedge \hat \delta (q_2, y') = q_1 \\ & \qquad ~ \wedge \hat \delta (q_1, w) = q_1 & & \wedge \hat \delta (q_2, w') = q_2 \\ \nonumber \\ & \qquad ~ \wedge \hat \delta (q_5, u) = q_3 & & \wedge \hat \delta (q_3, v) = q_5 \\ & \qquad ~ \wedge \hat \delta (q_3, w) = q_5 & & \wedge \hat \delta (q_5, w') = q_3 \\ \nonumber \\ & \qquad ~ \wedge \hat \delta (q_6, v) = q_4 & & \wedge \hat \delta (q_4, u) = q_6 \\ & \qquad ~ \wedge \hat \delta (q_4, w) = q_4 & & \wedge \hat \delta (q_6, w') = q_6 \\ \nonumber \\ & \qquad ~ \wedge \hat \delta (q_6, z) \in F \nLeftrightarrow \hat \delta (q_3, z) \in F \\ & \qquad ~ \wedge \hat \delta (q1, u) = q_3 \\ & \qquad ~ \wedge \hat \delta (q_2, v) = q_4 \end{align}\end{split}\]

algorithms1

algorithms1.alpha(s)

algorithms1.b1(dfa)

algorithms1.b12(dfa)

Parameters:dfa – Returns:

algorithms1.l1(dfa)

Parameters:dfa – Returns:

algorithms1.l12(dfa)

Parameters:dfa – Returns:

algorithms1.l1_1(dfa)

Parameters:ea – Returns:

algorithms1.l1_2(dfa)

algorithms1.l32(dfa)

algorithms2

algorithms2.b1(dfa)

Parameters:dfa – Returns:

algorithms2.b12(dfa)

Parameters:dfa – Returns:

algorithms2.l1(dfa)

algorithms2.l12(dfa)

Parameters:dfa – Returns:

algorithms2.l1_1(dfa)

algorithms2.l1_2(dfa)

algorithms2.l32(dfa)