PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 99(113) (2016), 177–191 DOI: 10.2298/PIM141227016A

CONTEXT-FREENESS OF THE LANGUAGES

OF SCHÜTZENBERGER AUTOMATA OF HNN-EXTENSIONS OF FINITE INVERSE SEMIGROUPS

Mohammed Abu Ayyash and Emanuele Rodaro

Abstract. We prove that the Schützenberger graph of any element of the HNN-extension of a finite inverse semigroup S with respect to its standard presentation is a context-free graph in the sense of [11 ], showing that the language L recognized by this automaton is context-free. Finally we explicitly construct the grammar generating L, and from this fact we show that the word problem for an HNN-extension of a finite inverse semigroup S is decidable and lies in the complexity class of polynomial time problems.

1. Introduction

The concept of HNN-extension has been originally introduced for groups in [6], where it has been showed that if A and B are two isomorphic subgroups of a group G, then it is possible to find a group H containing G such that A and B are conjugate to each other in H.

In this paper we consider inverse semigroups. A semigroup S is called inverse if for each element a ∈ S, there is a unique element a^{−1} ∈ S such that a = aa^{−1} a and a^{−1} = a^{−1} aa^{−1} ; a^{−1} is called the inverse of a. The presence of an inverse of each element of S suggests an easy generalization of the notion of HNNextension to inverse semigroups. However, in the category of inverse semigroups there is no analogue of Britton’s lemma, and inverse semigroups are not always embeddable in their HNN-extensions. To obtain the embeddability property for HNN-extensions of inverse semigroups, one must impose certain restrictions on the subsemigroups considered. For instance, in [7] one introduced a notion of

2010 Mathematics Subject Classification: 20M18, 20M35, 68Q45. Key words and phrases: inverse semigroup, Schützenberger automaton, context-free

language.

The second author acknowledges support from the European Regional Development Fund through the programme COMPETE and by the Portuguese Government through the FCT under the project PEst-C/MAT/UI0144/2013 and the support of the FCT project SFRH/BPD/65428/2009.

Communicated by Siniša Crvenković.

HNN-extension of a semigroup with unitary subsemigroups, other conditions on the subsemigroups have been considered for instance in [4, 16]. In the sequel we will concern with HNN-extensions in the sense of Yamamura, and the term HNNextension will be a synonymous of Yamamura’s HNN-extension.

The interest of mathematicians for inverse semigroups is naturally motivated by the fact that inverse semigroups may be regarded as semigroups of partial oneto-one transformations on a given set. More recently inverse semigroups have attracted also the attention of physics and computer science scholars because several notions and tools of inverse semigroup theory are attuned towards questions in solid-state physics (particularly those concerning quasi-crystals) and the concrete modeling of time-sensitive interactive systems (see for instance [8, 9, 10]). Besides, inverse semigroup theory gives rise to interesting algorithmic problems, and in the cases where such problems are decidable, the analysis of the computational complexity is a quite natural issue. Lastly, algorithmic problems on inverse semigroups are essentially problems on inverse word automata. A fundamental tool to study algorithmic issues in inverse semigroups is the notion of the Schützenberger automaton, introduced in [15]. An inverse semigroup S = Inv⟨Y |T ⟩, presented by a set Y of generators and a set T of relations, is the quotient of the free semigroup (Y ∪ Y^{−1} )^{+} by the least congruence τ that contains the Vagner relations and the relations in T. The notion of Schützenberger automaton A(Y, T; w) for a word w ∈ (Y ∪ Y^{−1} )^{+} relative to the presentation ⟨Y |T ⟩ of S is an extension of the notion of the Munn tree [12] for free inverse semigroups. The underlying graph SΓ(Y, T; w) of this automaton is the connected component of the Cayley graph of S containing wτ with respect to the presentation ⟨Y |T ⟩. The graph SΓ(Y, T; w) is an inverse word graph over Y, i.e., a connected graph whose edges are labelled over Y ∪ Y^{−1} in such a way that each edge labelled by x has a unique inverse edge labelled by x^{−1} . The Schützenberger automaton A(Y, T; w) is the deterministic (inverse) automaton having SΓ(Y, T; w) as underlying graph, and as initial and final states the vertices (ww^{−1} )τ, wτ, respectively. In [15] it is proven that these automata can be seen as the directed limit of a directed system of inverse word automata obtained, starting from the linear automaton of a word, by iteratively applying elementary expansions and determinations (edge foldings). The limit process ensures that the final automaton is closed with respect to the presentation ⟨Y |T ⟩, or equivalently, no more elementary expansions or determinations can be applied. One of the most remarkable feature of these automata is given by the fact that any two words w, w′ ∈ (Y ∪Y^{−1} )^{+} represent the same element of S if and only if A(Y, T; w) = A(Y, T; w′), or equivalently if and only if these automata accept the same language. Hence, Schützenberger automata are crucial in dealing with the word problem in the category of inverse semigroups, and the classification of their languages in conjunction with other language theoretical properties could be interesting to solve and analyze the computational complexity of some algorithmic issues. We refer to [14, 15] for any undefined notion and terminology.

HNN-EXTENSIONS OF INVERSE SEMIGROUPS VS CONTEXT-FREE LANGUAGES 179

In this paper we focus on the languages recognized by Schützenberger automata of HHN-extensions of finite inverse semigroups. We prove that the language recognized by the Schützenberger automaton of a word w with respect to the standard presentation of an HNN-extension [S, A, B, φ] is a deterministic context-free language. In [3] the analogous result for amalgams of finite inverse semigroups has been proven. The techniques involved in this paper are close to the ones used in [3], but they differ in several technical details. In some sense, HNN-extension seems a broader construction with respect to the amalgamated free product. Indeed, in [1] it is shown that any free product with amalgamation of two inverse semigroups can be always seen as a quotient of a special HNN-extension associated to it. From this result it appears that results that hold for amalgamated free products can be derived from the associated HNN-extensions. In our case, we have not been able to retrieve the case of amalgamated free product of finite inverse semigroups S_{1}, S_{2}, since the associated HNN-extension involves the free product S = S_{1} ∗ S_{2} which is clearly not finite. Therefore, in this direction it would be interesting to explore the case of HNN-extension [S_{1} ∗ S_{2}, A, B, φ] with S_{1}, S_{2}, A, B finite inverse semigroups, and look for the conditions for which the word problem in this structure is decidable.

The paper is organized as follows: in Section 2 we recall some basic notions and facts regarding the Schützenberger automata of HNN-extensions. Finally, in Section 3 we present the main results and we derive a polynomial time algorithm for the word problem.

2. Schützenberger automata of HNN-extensions of finite inverse semigroups

Definition 2.1. Let S = Inv⟨X|R⟩ ≃ (X ∪X^{−1} )^{+} /τ be an inverse semigroup,

and let φ : A → B be an isomorphism between the two inverse subsemigroups A, B of S. Let e, f ∈ S be two idempotents such that e ∈ A ⊆ eSe and f ∈ B ⊆ fSf (or e ∉ A ⊆ eSe and f ∉ B ⊆ fSf). Following [16], the inverse semigroup

S^{∗} = Inv⟨S, t | t^{−1} at = φ(a), t^{−1} t = f, tt^{−1} = e, ∀a ∈ A⟩

is called the HNN-extension of S associated with φ : A → B and it is denoted by [S; A, B; φ]. In the sequel we will denote S^{∗} = (X̄ ∪ X̄)^{∗}/ω the inverse semigroup with presentation ⟨X̄ | R_{HNN} ⟩ where X̄ = X ∪ {t} and R_{HNN} are the relations containing R and the linking relations t^{−1} at = φ(a), t^{−1} t = f, tt^{−1} = e, and we refer to this presentation as the standard presentation of S^{∗}.

In this section we give a geometric description of A(X̄, R_{HNN} ; w), w ∈ (X̄ ∪ X̄^{−1} )^{+} . First we introduce some terminology from [14]. Let Γ = (V (Γ), E, X̄) be a deterministic inverse word graph on X̄, where V (Γ) is the set of vertices, E ⊆ V (Γ)×(X̄ ∪X̄^{−1} )×V (Γ) is the set of edges with the property that if (v, a, v′), a ∈ X̄ ∪ X̄^{−1} , is an edge, then (v′, a^{−1} , v) is also an edge of Γ, and the determinism is expressed by the following condition: if (v, a, p), (v, a, p′) ∈ E then p = p′. Since Γ is deterministic, for any v_{1}, v_{2} ∈ V (Γ) and u ∈ (X̄ ∪ X̄^{−1} )^{+} , there is at most one path (v_{1}, u, v_{2}) connecting v_{1} to v_{2} labelled by u. A subgraph Δ of Γ, with at least one edge is called S-lobe (or lobe for short) if it is a maximal connected inverse subgraph on X. With a slight abuse of notation we say that in some S-lobe Δ there is a path (v_{1}, s, v_{2}), for some s ∈ S, if there is some u ∈ (X ∪ X^{−1} )^{+} with uω = s such that (v_{1}, u, v_{2}) is a path in Δ. Note that since S is a finite inverse semigroup, there are finitely many (up to isomorphism) possible S-lobes which are quotients of Schützenberger automata of elements of S with respect to the presentation ⟨X|R⟩. A t-edge is an edge of Γ labelled by t. Two vertices v_{1}, v_{2} are called t-adjacent (for short adjacent) if they are connected by a t-edge, i.e., if either (v_{1}, t, v_{2}) or (v_{2}, t, v_{1}) are edges of Γ. A t-edge is called extremal if it has a vertex belonging neither to an S-lobe nor to another t-edge. Two S-lobes Δ_{1}, Δ_{2} are called adjacent if there are two t-adjacent vertices v_{1} ∈ V (Δ_{1}) and v_{2} ∈ V (Δ_{2}), each of these vertices is called an intersection vertex of Γ. If there is an edge (v_{i}, t, v_{i+1} ), then the ordered pair (v_{i}, v_{i+1} ) is called an intersection pair. The lobe graph of the inverse word graph Γ is the directed graph G(Γ) whose vertices are the S-lobes of Γ and there is a directed edge d = (Δ_{1}, Δ_{2}) from a lobe Δ_{1} to a lobe Δ_{2} whenever there is an intersection pair (v_{1}, v_{2}) with v_{1} ∈ V (Δ_{1}) and v_{2} ∈ V (Δ_{2}). In [14] five constructions are described whose iterative application, starting from the linear automaton of a word w ∈ (X̄ ∪ X̄^{−1} )^{∗} , generate a directed system of inverse word automata whose directed limit is the Schützenberger automaton A(X̄, R_{HNN} ; w). These constructions are formed by grouping in some order some elementary expansions and determinations. The iterative application of the first four constructions end after a finite number of steps with a finite inverse word automaton on X̄, called t-Core(w) whose underlying inverse word graph has a particular shape called t-opuntoid which is characterized by the following properties:

• each S-lobe is closed (with respect to ⟨X|R⟩) and it is a quotient of some Schützenberger automaton for some element of S;

• the lobe graph is a directed tree;

• it has the t-saturation property, i.e., for each path (ν, a, ν′), with a ∈ A, there are two edges (ν, t, ν^{∗}), (ν′, t, (ν′)^{∗}), and for each path (ν, b, ν′), with b ∈ B, there are two edges (ν^{∗}, t, ν), ((ν′)^{∗}, t, ν′);

• it has the t-assimilation property, i.e., for any intersection pair (v_{1}, v_{2}) belonging to the adjacent lobes Δ_{1}, Δ_{2} we have that (v_{1}, a, v), a ∈ A, is a path in Δ_{1} if and only if (v_{2}, φ(a), v′) is a path in Δ_{2} and (v, v′) is also an intersection pair.

Note that the geometric realization of an opuntoid graph with the usual graph theoretical distance is actually a hyperbolic space since it is not difficult to show that the triangles are |S|-slim. An inverse word subgraph Γ′ of Γ is called tsubopuntoid if Γ′ is a t-opuntoid graph and its lobes are also lobes of Γ. In general t-Core(w) is not closed with respect to ⟨X̄|R_{HNN} ⟩. Indeed, an expansion must be applied to any vertex of t-Core(w) which belongs to an extremal t-edge but not to a lobe. More precisely, if (v, t, v′) is the extremal t-edge, and a ∈ A labels a loop at v, then we perform an expansion relative to the relation of the form t^{−1} at = φ(a); in case the extremal t-edge is of the form (v′, t, v) and b ∈ B labels a loop at v, then the performed expansion is relative to a relation of the form t^{−1} φ^{−1} (b)t = b. We make a distinction between the two ending vertices v, v′ of the extremal t-edge (v, t, v′) by calling the vertex v in the S-lobe a bud, while for the other vertex v′ a t-bud. Note that a bud can be a vertex of a t-edge, which is not extremal, while a t-bud always belongs to an extremal t-edge. An opuntia is a t-opuntoid graph having a unique S-lobe, for an S-lobe Δ we denote by O_{p}(Δ) the smallest t-opuntoid containing an isomorphic copy of Δ, i.e., O_{p}(Δ) is obtained by taking an isomorphic copy of Δ and adding all the t-edges to respect the t-saturation property. In a t-opuntoid Γ, if v is a bud of Γ,then at least one among the following two sets: L_{A}(v, Δ) = {a ∈ A : (v, a, v) is a loop at v} and L_{B}(v, Δ) = {b ∈ B : (v, b, v) is a loop at v} is nonempty, and in the corresponding nonempty set we use f_{A}(v, Δ) (f_{B}(v, Δ)) to denote the least idempotent in L_{A}(v, Δ) (L_{B}(v, Δ)). In [14] it is proven that a specific finite series of expansions and determinations, called Construction 5, applied to a t-bud v of a t-opuntoid Γ generates (after finitely many steps) a new t-opuntoid Γ′obtained from Γ by adding a new opuntia connected to v by a t-edge whose direction depends on which one between L_{A}(v, Δ) and L_{B}(v, Δ) is nonempty. This construction can be applied iteratively to obtain a directed system of t-opuntoid automata. Moreover, it is proven in [14] that the direct limit of such a system is A(X̄, R_{HNN} ; w). Because this construction plays an important role in the sequel, we briefly recall it here:

Construction 5: 1) Let (α, Γ, β) be an t-oputoid automaton and let (v, y, v′) be an extremal edge with y ∈ {t, t^{−1} }, such that v is a bud and v′ is its corresponding t-bud for Γ. Assume that v ∈ V (Δ) for some lobe Δ of Γ, and assume that L_{A}(v, Δ) ≠ ∅, (the other case L_{B}(ν, Δ) ≠ ∅ is analogous). Let (x, Σ, x) be the Schützenberger automaton of φ(f_{A}(v, Δ)) relative to ⟨X|R⟩, and consider the set:

N(x, Σ) = {y ∈ V (Σ)|(x, φ(u), y) : is a path in Σ for some u ∈ L_{A}(v, Δ)}

Let ρ be the least equivalence relation on V (Σ) which identifies all the elements of N(x, Σ) with x and such that Σ/ρ is deterministic and put Δ′ = Σ/ρ. It can be proven that Δ′ is a finite inverse word graph closed with respect ⟨X|R⟩ such that φ(L_{A}(v, Δ)) = L_{B}(xρ, Δ′).

2) In [14] it is proven that there is a one-to-one correspondence between the sets

B_{Δ} = {p ∈ V (Δ) : (v, a, p) is a path in Δ for some a ∈ A}
R_{Δ′} = {p′ ∈ V (Δ′) : (xρ, φ(a), p′) is a path in Δ′ for some a ∈ A}

given by the map ψ : B_{Δ} → R_{Δ′} which associates to a vertex p in B_{Δ} , such that (v, a, p) is a path in Δ for some a ∈ A, the vertex p′for which (xρ, φ(a), p′) is a path in Δ′. Then form the inverse word graph Γ′ = (v, Γ, v)×(xρ, Δ′, xρ) defined by the disjoint union of (v, Γ, v), (xρ, Δ′, xρ) identifying xρ with the t-bud v′, and adding all the t-edges (p, t, ψ(p)) for all p ∈ B_{Δ} . Moreover, to maintain the t-opuntoid structure we need to satisfy the t-saturation property, thus for each vertex q such that L_{A}(q, Δ′) ≠ ∅ (L_{B}(q, Δ′) ≠ ∅) we add the extremal t-edge (q, t, q′) ((q, t^{−1} , q′)). In Γ′ any vertex v ∈ B_{Δ} with its corresponding vertex ψ(v) ∈ R_{Δ′} will form an intersection pair of vertices (v, ψ(v)) (or (ψ(v), v) in the case L_{B}(ν, Δ) ≠ ∅) between the lobes Δ and Δ′. The set R_{Δ′} is called the root set of Δ′, and it is uniquely determined by the t-buds in which Construction 5 is applied. For two generic

opuntias O_{P}(Δ), O_{p}(Δ′) we write O_{P}(Δ) −⟶^{p,t,q} O_{p}(Δ′) (O_{P}(Δ) −−−−→^{p,t^{−1} ,q} O_{p}(Δ′)),

for short Δ −⟶^{p,t,q} Δ′ (Δ −−−−→^{p,t^{−1} ,q} Δ′), whenever applying Construction 5 to the t − bud q such that (p, t, q) (or (p, t^{−1} , q)) is an extremal t-edge with bud p ∈ V (Δ) we obtain a t-opuntoid graph consisting of two adjacent S-lobes Δ, Δ′. An Slobe which results from the application of Construction 5 is called an external lobe. We call external lobe type of the standard presentation ⟨X̄|R_{HNN} ⟩ of an HNNextension of a finite inverse semigroup, any pair (Ω, Ξ) where Ω is a deterministic inverse word graph which is a quotient of a Schützenberger automaton of some idempotent of A or B with respect to ⟨X|R⟩, and Ξ ⊆ V (Ω) is a maximal subset of vertices connected to each other by paths labelled by elements of A (or by elements of B). Since S is finite, it is straightforward to see that there are finitely many (up to isomorphism) external lobe types. Therefore, we can order them as pairs: (Ω_{1}, Ξ_{1}), (Ω_{2}, Ξ_{2}), …, (Ω_{K} , Ξ_{K}), such that there is an injective map σ from the set of the external lobes of SΓ(X̄, R_{HNN} ; w) into the set {1, 2, ..., K} such that for any external lobe Δ of SΓ(X̄, R_{HNN} ; w) there is an isomorphism η_{Δ} between Δ and Ω_{σ(Δ)} with η_{Δ} (R_{Δ} ) = Ξ_{σ(Δ)} . The integer σ(Δ) is called the type of the external lobe Δ. We also add to the previous set of external lobe types the element (Ω_{0}, Ξ_{0}) where Ω_{0} is the underlying graph of t-Core(w), Ξ_{0} = {∅}. By convention η_{Ω_{0}} is the identity. We denote by B_{j}, with 0 ⩽ j ⩽ K the set of buds of Ω_{j}. We refer to the pair (Ω_{j} , Ξ_{j}) as the lobe of type j. If Construction 5 is applied to an opuntia O_{p}(Δ) at an extremal t-edge (ν, y, ν′) with ν ∈ V (Δ) yielding an external opuntia O_{p}(Δ′) with ν′ ∈ V (Δ′), then there are two lobe types Ω_{h}, Ω_{k} with 0 < h ⩽ K and 0 ⩽ k ⩽ K, and two graph isomorphisms η_{Δ} and η_{Δ′} such that η_{Δ} (Δ) = Ω_{k}, η_{Δ} (ν) = p, and η_{Δ′} (Δ) = Ω_{h}, η_{Δ′} (ν′) = q, where p ∈ B_{k} and q ∈ Ξ_{h}. Accordingly, we say that the lobe type Ω_{h} feeds off the lobe type Ω_{k}, and

we write it as k −⟶^{p,t,q} h (k −−−−→^{p,t^{−1} ,q} h). Intuitively A(X̄, R_{HNN} ; w) is built starting from Ω_{0} by iteratively patching suitable lobes from {Ω_{1}, …, Ω_{K} }. More precisely, if Γ is the t-opuntoid graph obtained by this patching procedure at a certain step, then if (ν, y, ν′), y ∈ {t, t^{−1} }, is an extremal t-edge with ν ∈ V (Δ), for some external lobe Δ of type k, then at the next step we add an opuntia O_{p}(Δ′), for some S-lobe

Δ′ of type h whenever the condition k −−−→^{p,y,p′} h with η_{Δ} (ν) = p, η_{Δ′} (ν′) = p′ holds.

Let Δ be an external lobe of SΓ(X, R; w) and let ν ∈ R_{Δ} and let Δ′ be the adjacent lobe of Δ in ν; according to [13] we call feed off branch (for short branch) of Δ the t-subopuntoid subgraph Br(Δ) of SΓ(X, R; w) whose underlying lobe tree is the connected component of G(SΓ(X̄, R_{HNN} ; w)) ∖ {Δ′} containing Δ. Since the S-lobes in Br(Δ) are built applying iteratively Construction 5, which is defined locally, it is not difficult to check that the following lemma, analogous to the remark at the beginning of Section 3 of [13], holds.

Lemma 2.1. Two external lobes of SΓ(X̄, R_{HNN} ; w) of the same type have isomorphic branches. Hence, in SΓ(X̄, R_{HNN} ; w) there are only finitely many branches up to isomorphism.

Definition 2.2. For a word w ∈ (X̄ ∪X̄^{−1} )^{∗}, ∥w∥ denotes the number of t and t^{−1} occurring in w, obviously ∥w∥ ⩽ |w|. Let (α, Γ, β) be a t-opuntoid automaton, and let ν ∈ V (Γ), the norm ∥ν∥ of ν is ∥u∥ where u is the word labelling the shortest path connecting α to ν. Note that, since each S-lobe Δ of the t-opuntoid automaton (α, Γ, β) is a connected graph and the lobe graph is a tree, then all the vertices of an S-lobe Δ have the same norm. Hence we can define the norm ∥Δ∥ of the S-lobe Δ as the norm of any vertex in V (Δ). The distance between two vertices ν_{1}, ν_{2} ∈ V (Γ) is the length of the shortest word labelling a path connecting ν_{1} to ν_{2} and it is denoted by d(ν_{1}, ν_{2}), as usual, such shortest paths are called geodesics. Note that in particular ∥ν∥ ⩽ d(α, ν) holds.

3. Context-freeness of the Schützenberger automata of an HNN-extension of finite inverse semigroups

In this section we prove that the Schützenberger graph SΓ(X̄, R_{HNN} ; w) of each word w ∈ (X̄ ∪ X̄^{−1} )^{+} relative to the standard presentation ⟨X̄|R_{HNN} ⟩ of an HNN-extension of a finite inverse semigroup is a context-free graph in the sense of [11]. Moreover, we give an alternative proof of this fact by directly constructing the grammar of the pushdown automaton recognizing the same language of A(X̄, R_{HNN} ; w). This gives an alternative proof of the decidability of the word problem for S^{∗} already proved with other techniques in [14], and then, using the well known fact that the membership problem for deterministic context-free languages can be solved in a linear time, we show that the word problem can be solved by a polynomial-time algorithm. First we recall some definitions.

Definition 3.1. [11] A finitely generated graph is a labelled graph Γ having the following properties:

• Γ is a connected graph with a distinguished vertex ν_{0}, called the origin of Γ;

• Γ has a fixed upper bound on the degree of vertices;

• The label alphabet of Γ is finite.

Since the alphabet X̄ ∪ X̄^{−1} is finite and SΓ(X̄, R_{HNN} ; w) is deterministic, then pinpointing the initial state α = (ww^{−1} )ω of A(X̄, R_{HNN} ; w) as distinguished vertex, we can view SΓ(X̄, R_{HNN} ; w) as a finitely generated graph.

Let Γ be a finitely generated graph with origin ν_{0}. For n ⩾ 0, Γ_{n} denotes the subgraph of Γ consisting of all the vertices whose distance from ν_{0} is less than n. We use Λ(ν) to denote the connected component of Γ ∖ Γ_{n} which contains ν. A vertex p of Λ(ν) is called a frontier point of Λ(ν) if d(ν_{0}, p) = n, the set of frontier points of Λ(ν) will be denoted by Φ(ν). Since Γ has uniformly bounded degree each set Φ(ν) is finite. By the connectedness property we have Λ(ν) = Λ(μ) if and only if Φ(ν) = Φ(μ).

Let ν_{1} and ν_{2} be vertices of Γ. An end-isomorphism between the two subgraphs Λ(ν_{1}) and Λ(ν_{2}) is a label preserving graph isomorphism ψ : Λ(ν_{1}) → Λ(ν_{2}) such that ψ(Φ(ν_{1})) = Φ(ν_{2}). Of course an end-isomorphism is a V -isomorphism according to [15].

Definition 3.2. Let Γ = SΓ(X̄, R_{HNN} ; w) be the Schützenberger graph of w ∈ (X̄ ∪ X̄^{−1} )^{+} and let ν ∈ V (Γ). For every μ ∈ Λ(ν) let Δ(μ) denote the S-lobe of Γ which contains μ. An S-lobe Δ(μ) with minimum norm among the S-lobes Δ(μ) with μ ∈ Λ(ν) is called the base of the subgraph Λ(ν) and it is denoted by B(ν).

The base has the following property.

Proposition 3.1. With the above definition, the base B(ν) is unique,

V (Λ(ν)) ∩ V (B(ν)) ≠ ∅

and Λ(ν) is contained in Br(B(ν)). Furthermore, if p ∈ V (B(ν)), then for any q ∈ Φ(ν) we have:

d(p, q) ⩽ 2|S|

Proof. Since Λ(ν) is connected, each path in Λ(ν) connecting any two vertices in Λ(ν) induces a lobe path in G(Γ). Therefore, the subgraph Ω of G(Γ) formed by all the lobes Δ(μ) with μ ∈ Λ(ν) is a subtree of G(Γ) and there is a unique lobe in Ω with minimum norm, corresponding to B(ν). If Δ′ denotes the lobe adjacent to B(ν) with norm ∥B(ν)∥−1, it is evident that Ω is contained in the lobe graph whose underlying lobe tree is the connected component of Γ∖{Δ′} containing B(ν). This corresponds to the fact that Λ(ν) is contained in Br(B(ν)). As a direct consequence of the definition of the base we get V (Λ(ν)) ∩ V (B(ν)) ≠ ∅. Let us prove the last statement of the proposition. Since each lobe Δ is a quotient of a Schützenberger automaton of some element in S, and the vertices of a Schützenberger automaton of a word w are the elements of the R-class of the element of S represented by w, we have

max{d(v, v′) : v, v′ ∈ V (Δ)} ⩽ |S|.

Suppose that (α, u, q) is a geodesic connecting α to q. Since G(Γ) is a tree and the base B(ν) is the lobe with smallest norm containing an element of Λ(ν), there is at least a vertex q′ ∈ V (B(ν)) belonging to the path (α, u, q). Therefore, if n = d(α, ν) and p′ ∈ V (Λ(ν)) ∩ V (B(ν)), we get

n ⩽ d(α, p′) ⩽ d(α, q′) + d(q′, p′) ⩽ d(α, q′) + |S|

where in the last inequality we have used d(q′, p′) ⩽ |S|. Hence d(α, q′) ⩾ n − |S|, and since q′ belongs to the geodesic (α, u, q) we also have n = d(α, q) = d(α, q′) + d(q′, q), from which we get d(q′, q) ⩽ |S|. Therefore we have the claim d(p, q) ⩽ d(p, q′) + d(q′, q) ⩽ 2|S|. □

To prove the main theorem we need to consider a subset of vertices of V (Λ(ν)) larger than the set of frontier points Φ(ν). The following set

N (ν) = {q ∈ V (Λ(ν)) : ∃p ∈ Φ(ν), d(p, q) ⩽ 4|S|}

is called the S-neighbor of ν. This set essentially determines Λ(ν) up to isomorphism as the following lemma shows.

Lemma 3.1. With the above notation, let ψ : Br(B(ν)) → Br(B(ν′)) be an isomorphism such that ψ(N (ν)) = N (ν′) and ψ(Φ(ν)) = Φ(ν′), then the restriction ψ : Λ(ν) → Λ(ν′) is also an isomorphism.

Proof. Since ψ(N (ν)) = N (ν′), it is enough to prove that for any vertex p ∈ Λ(ν) with d(q, p) ⩾ 4|S| for any q ∈ Φ(ν), we have ψ(p) ∈ V (Λ(ν′)). In fact, to show that ψ : Λ(ν) → Λ(ν′) is an isomorphism it is enough to consider ψ^{−1} and repeat the argument. To prove that ψ(p) ∈ V (Λ(ν′)) it is enough to show that d(α, ψ(p)) ⩾ m with m = d(α, ν′). Indeed, assume, contrary to the claim, that there is a path (p′, u, p) with p′ ∈ Φ(ν) such that ψ(p) ∉ V (Λ(ν′)) and d(α, ψ(p)) ⩾ m. Without loss of generality we can take the path of minimal length with this property. Thus, if u = wa, for some a ∈ X̄ ∪ X̄^{−1} , w ∈ (X̄ ∪ X̄^{−1} )^{∗}, then the vertex p′′ such that (p′, w, p′′) is a path in Γ has the property that ψ(p′′) ∈ V (Λ(ν′)) and d(α, ψ(p′′)) ⩾ m. Hence, by the connectedness of Λ(ν′) we get ψ(p) ∈ V (Λ(ν′)), a contradiction.

We devote the rest of the proof to prove the claim d(α, ψ(p)) ⩾ m. Let (α, u_{1}, p′), (p′, u_{2}, p) be two geodesics with p′ ∈ Φ(ν). Since ψ(Φ(ν)) = Φ(ν′), ψ(p′) ∈ Φ(ν′), then there is a geodesic (α, w_{1}, ψ(p′)), and it is easy to see that (ψ(p′), u_{2}, ψ(p)) is also a geodesic. Let (α, h, ψ(p)) be a geodesic, since G(Γ) is a tree, by Proposition 3.1 there is a vertex s ∈ V (B(ν′)) belonging to the geodesic (α, h, ψ(p)). By the triangular inequality we have:

d(p′, p) = d(ψ(p′), ψ(p)) ⩽ d(s, ψ(p)) + d(s, ψ(p′)) ⩽ d(s, ψ(p)) + 2|S|

where the last inequality follows by d(s, ψ(p′)) ⩽ 2|S|, since by Proposition 3.1 s ∈ V (B(ν′)) and ψ(p′) ∈ Φ(ν′). Thus, since (α, h, ψ(p)) is a geodesic, we get:

(3.1)  d(α, s) = d(α, ψ(p)) − d(s, ψ(p)) ⩽ d(α, ψ(p)) − d(p, p′) + 2|S|.

Using again the triangular inequality we get:

(3.2)  m = d(α, ψ(p′)) ⩽ d(α, s) + d(s, ψ(p′)) ⩽ d(α, s) + 2|S|

where again we have used Proposition 3.1 in the last inequality. By inequalities (3.1), (3.2) we get:

d(α, ψ(p)) ⩾ d(α, s) + d(p, p′) − 2|S| ⩾ m + d(p, p′) − 4|S|.

Hence, since p′ ∈ Φ(ν) and by the condition d(q, p) ⩾ 4|S| for any q ∈ Φ(ν) assumed at the beginning, we get d(p, p′) ⩾ 4|S|, whence the claim d(α, ψ(p)) ⩾ m. □

We recall the following definition.

Definition 3.3. [11] A graph Γ is context-free if it is a finitely generated graph such that the set {Λ(ν) : ν ∈ V (Γ)} has only finitely many isomorphism classes under end-isomorphisms.

Theorem 3.1. Let [S; A, B] be an HNN-extension of finite inverse semigroups S = ⟨X|R⟩ and let w ∈ (X̄ ∪ X̄^{−1} )^{+} . The Schützenberger graph SΓ(X̄, R_{HNN} ; w) is a context-free graph.

Proof. Since Γ = SΓ(X̄, R_{HNN} ; w) is a finitely generated graph, it remains to prove that the set C = {Λ(ν) : ν ∈ V (Γ)} has only finitely many isomorphism classes under end-isomorphisms. Since t-Core(w) is finite, there are finitely many subgraphs Λ(ν) of the collection C for which V (Λ(ν))∩V (t−Core(w)) ≠ ∅. Therefore, it is enough to prove that the subset C′ of C formed by the subgraphs Λ(ν) for which B(ν) is an external lobe, has only finitely many isomorphism classes under end-isomorphisms. By Lemma 2.1 Γ has finitely many branches of external lobes up to isomorphisms. Therefore, by Lemma 3.1 the possible elements of C′ up to end-isomorphism are determined by the possible S-neighbors. By Proposition 3.1 the frontier points are located at a distance of at most 2|S| with respect to any vertex in a base lobe. Hence by the definition the vertices of an S-neighbor are located at a distance of at most 6|S| from any vertex of a base lobe, whence the possible configurations of the S-neighbors are finitely many up to isomorphism. □

We recall the following standard definition.

Definition 3.4. Let P = (Q, Σ, Θ, η, q_{0}, ⊥, F) be a pushdown automaton with input alphabet Σ, stack alphabet Θ, transition relation η, initial state q_{0} ∈ Q, set of final states F ⊆ Q, and initial stack element ⊥. As usual, a configuration of P is a triple (q, γ, z) with q ∈ Q, γ ∈ Θ^{+} ∪ {⊥} and z ∈ Σ^{∗}. We denote by ⊧ one step of computation of P, (q, bγ, xz) ⊧ (q′, uγ, z), x ∈ Σ ∪ {ϵ}, b ∈ Θ, u ∈ Θ^{∗} if (q′, u) ∈ η(q, x, b). By ⊧^{n} we denote a computation of n steps, and by ⊧^{∗} the reflexive and transitive closure of ⊧. The transition graph of P is the labelled digraph on Σ whose vertices are the possible configurations of P such that there is an edge labelled by a ∈ Σ from the vertex v_{1} to the vertex v_{2} if and only if, reading the letter a, the pushdown automaton moves from the configuration v_{1} to the configuration v_{2}.

The following well known result links transition graphs of pushdown automata with context-free graphs.

Theorem 3.2. [11] A finitely generated graph Γ is context-free if and only if Γ is the transition graph of some pushdown automaton.

We therefore obtain the following result.

Corollary 3.1. Let [S; A, B] be an HNN-extension of finite inverse semigroup S = ⟨X|R⟩ and let w ∈ (X̄ ∪ X̄^{−1} )^{+} ; then the language recognized by the Schützenberger automaton A(X̄, R_{HNN} ; w) is a context-free language.

We now build directly a pushdown automaton that recognizes the language L = L[A(X̄, R_{HNN} ; w)]. Such a direct approach is useful when dealing with the complexity issue of the word problem.

Since the lobe graph G(SΓ(w)) of SΓ(X̄, R_{HNN} ; w) is a tree, for each pair of lobes Δ, Δ′ of A(X̄, R_{HNN} ; w) there is a unique reduced lobe path

Δ = Λ_{0}, …, Λ_{n} = Δ′

connecting Δ to Δ′. When we consider the underlying graph Ω_{0} of Core(w) as a unique lobe, we call geodesic from a lobe Δ to the “lobe” Ω_{0} the shortest reduced lobe path of G(SΓ(w)) from Δ to some lobe of Ω_{0}. If Δ is not an external lobe we assume that the geodesic is formed by the unique lobe Δ itself. Let Λ_{s}, Λ_{s−1} , …, Λ_{0} be such a geodesic, where Λ_{0} is a lobe of the t-subopuntoid graph Ω_{0} and Λ_{s} = Δ. If s > 0, each Λ_{i+1} is obtained from Λ_{i} by applying Construction 5 at some bud ν_{i} ∈ V (Λ_{i}) forming the intersection pair (ν_{i}, ν_{i+1} ) (or (ν_{i+1} , ν_{i})), where ν_{i+1} ∈ V (Λ_{i+1} ).

Definition 3.5. For each geodesic Λ_{s}, Λ_{s−1} , …, Λ_{0} of A(X̄, R_{HNN} ; w) we call

geodesic type a sequence of 5-tuples:

(j_{s−1} , j_{s}, p_{s−1} , y_{s}, q_{s})(j_{s−2} , j_{s−1} , p_{s−2} , y_{s−1} , q_{s−1} ) …(j_{2}, j_{3}, p_{2}, y_{3}, q_{3})

(j_{1}, j_{2}, p_{1}, y_{2}, q_{2})(0, j_{1}, p_{0}, y_{1}, q_{1})(0, 0, α, −, α)

• for each i with 0 ⩽ i ⩽ s, j_{i} is the type of the lobe Λ_{i} of the geodesic and so according to our convention j_{0} = 0;

• for each i with 1 ⩽ i ⩽ s, y_{i} ∈ {t, t^{−1} };

• for each i with 1 ⩽ i ⩽ s, j_{i−1} −−−−−−→^{p_{i−1} ,y_{i} ,q_{i}} j_{i};

• for each i with 1 ⩽ i ⩽ s there is an isomorphism η_{Λ_{i}} from Λ_{i} onto Ω_{j_{i}} such that for i ⩾ 2 (η_{Λ_{i−1}}^{−1} (p_{i−1} ), y_{i}, η_{Λ_{i}}^{−1} (q_{i})) is a t-edge connecting Λ_{i−1} to Λ_{i}, and for i = 1 we have the t-edge (p_{0}, y_{i}, η_{Λ_{1}}^{−1} (q_{1})) connecting a lobe of Ω_{0} to Λ_{1}.

If (α, z, ν) is a path of A(X̄, R_{HNN} ; w), we call geodesic type associated with the path (α, z, ν) a geodesic type from the lobe Δ containing ν to Ω_{0}. Note that, since two adjacent lobes have in general more than one intersection pairs, there are also many geodesic types associated to a given path, all of them are formed by sequences of 5-tuples having the same length and for all i the i-th tuples of the sequences have the same first two components. In the following definition we describe the pushdown automaton which simulates the behavior of A(X̄, R_{HNN} ; w).

Definition 3.6. The pushdown automaton associated with A(X̄, R_{HNN} ; w) is the automaton P_{w} = (Q, X̄ ∪ X̄^{−1} , Σ_{w}, δ, q_{0}, ⊥, F) where:

• Q = ⋃ _{h∈[0,K]} V (Ω_{h}) is the (finite) set of states;

• X̄ ∪ X̄^{−1} is the input alphabet;

• Σ_{w} = {(i, j, p, y, q) : i, j ∈ [0, K], p ∈ B_{i}, q ∈ Ξ_{j} , i −⟶^{p,y,q} j, y ∈ {t, t^{−1} }}

is the (finite) stack alphabet, whose elements in the sequel will be often denoted by capital letters;

• q_{0} = α ∈ V (Ω_{0}) is the initial state;

• ⊥= (0, 0, α, −, α) is the initial stack symbol;

• F = {β} with β ∈ V (Ω_{0}) is the final state of A(X̄, R_{HNN} ; w);

• δ : Q × (X̄ ∪ X̄^{−1} ) × Σ_{w} → Q × Σ_{w}^{∗} is the transition function defined as following. Let M = (i, j, p, y, q) ∈ Σ_{w}, x ∈ X ∪ X^{−1} and q_{1}, q_{2} ∈ Q then:

(1) Inside a lobe. If (q_{1}, x, q_{2}) is an edge of the lobe Ω_{j}, then δ(q_{1}, x, M) = (q_{2}, M).

(2) Pass into a new lobe. If (q_{1}, x, q_{2}) is not an edge of the lobe Ω_{j} (i.e., x ∈ {t, t^{−1} }), and either x ≠ y^{−1} or q_{1} ∉ Ξ_{j}, then δ(q_{1}, x, M) = (q_{2}, NM) with

N = (j, h, q_{1}, x, q_{2}) if and only if j −−−−→^{q_{1} ,x,q_{2}} h.

(3) Go back into a yet visited lobe. If (q_{1}, x, q_{2}) is not an edge of the lobe Ω_{j} with x = y^{−1} and q_{1} ∈ Ξ_{j}, if y = t^{−1} (y = t) let (q, u, q_{1}) be a path of Ω_{j} for some u ∈ A (u ∈ B), then δ(q_{1}, x, M) = (q_{2}, ϵ) where q_{2} is the vertex of Ω_{i} such that (p, φ(u), q_{2}) (or (p, φ^{−1} (u), q_{2})) is a path in Ω_{i}.

We remark that since the construction of P_{w} depends on the edges of the automaton A(X̄, R_{HNN} ; w) which is deterministic, then P_{w} is a deterministic pushdown automaton.

Theorem 3.3. With the above definitions L[A(X̄, R_{HNN} ; w)] = L[P_{w}].

Proof. We show that a word z ∈ (X̄ ∪ X̄^{−1} )^{+} labels a path (α, z, ν) in A(X̄, R_{HNN} ; w) if and only if there is a computation

(q_{0}, ⊥, zz′) ⊧^{∗} ( q, ∏_{j=k}^{1} M_{j} ⊥, z′)

of P_{w} where z′ ∈ (X̄ ∪ X̄^{−1} )^{∗} and ∏ _{j=k}^{1} M_{j} is the geodesic type associated to the path (α, z, ν).

Let us prove the “only if part”. Assume that (q_{0}, ⊥, zz′) ⊧^{n} (q, γ, z′) is a computation of P_{w} with z′ ∈ (X̄ ∪ X̄^{−1} )^{∗}, γ = ∏ _{j=k}^{1} (h_{j−1} , h_{j} , p_{j−1} , y_{j} , q_{j}) ⊥. We prove by induction on n that there is lobe Δ of type h_{k} and a vertex ν ∈ V (Δ) such that q = η_{Δ} (ν) and (α, z, ν) is the path of A(X̄, R_{HNN} ; w) with γ as associated geodesic type. If n = 1, then the computation consists of a unique transition that can be either of type (1) or of type (2). In the first case the transition is performed in t-Core(w) with q ∈ V (Ω_{0}), γ =⊥, z ∈ X̄ ∪ X̄^{−1} , (q_{0}, z, q) ∈ E(Ω_{0}) and the geodesic type associated to the path (q_{0}, z, q) is (0, 0, α, −, α). If the computation is of type (2), then γ = (0, h_{1}, α, y_{1}, q) ⊥ with 0 −−⟶^{α,y_{1} ,q} h_{1}, q ∈ Ξ_{h_{1}} and z = y_{1}. Therefore, there exist a vertex q_{0} ∈ V (Ω_{0}) and an external lobe Δ of type h_{1}, such that η_{Δ} (Δ) = Ω_{h_{1}} , η_{Δ} (R_{Δ} ) = Ξ_{h_{1}} for some graph isomorphism η_{Δ} such that (η_{Δ}^{−1} (q_{0}), z, η_{Δ}^{−1} (q)) is a t-edge connecting a lobe of Ω_{0} with Δ. Hence the statement is satisfied because (0, h_{1}, α, y_{1}, q)(0, 0, α, −, α) is the geodesic type associated to the path (α, z, η_{Δ}^{−1} (q)).

Suppose that the statement holds for each derivation of length n−1 and consider a derivation of length n, let z′′az′ ∈ (X̄∪X̄^{−1} )^{+} where z′′∈ (X̄∪X̄^{−1} )^{+} , |z′′| = n−1 and a ∈ X̄ ∪ X̄^{−1} . Since at each step of the computation an input character is read, we have:

(q_{0}, ⊥, zz′) = (q_{0}, ⊥, z′′az′) ⊧^{n−1} (q′, γ′, az′) ⊧ (q, γ, z′),

where z = z′′a and γ′ = ( ∏ _{j=s}^{1} (h_{j−1} , h_{j} , p_{j−1} , y_{j} , q_{j})) ⊥ for some s ⩽ n − 1.

By induction hypothesis there are a lobe Δ′ of A(X̄, R_{HNN} ; w) and a vertex ν′ ∈ V (Δ′) such that η_{Δ′} (ν′) = q′ and (α, z′′, ν′) is a path of the Schützenberger automaton whose associated geodesic type is the sequence γ′. We now consider the n-th step which could be any one of the transitions defined in P_{w}. We consider the following cases.

i) Suppose that the transition uses the rule (1), then q′, q ∈ V (Ω_{h_{s}} ) and (q′, a, q) ∈ E(Ω_{h_{s}} ). So there is a vertex ν ∈ V (Δ′) such that η_{Δ′} (ν) = q and (ν′, a, ν) ∈ E(Δ′). Hence γ′ = γ is the geodesic type associated to both (α, z′′a, ν) and (α, z′′, ν′). Thus (α, z, ν) is the path in A(X̄, R_{HNN} ; w) corresponding to the computation (q_{0}, ⊥, zz′) ⊧^{∗} (q, γ, z′).

ii) Assume that the n-th step of the computation uses rule (2). Let M = (h_{s}, h_{s+1} , q′, y_{s+1} , q) be the item that is pushed into the stack according to the computation (q′, γ′, az′) ⊧ (q, Mγ′, z′), then we have two possibilities: q′ ∉ Ξ_{h_{s}}

hence q′ ∈ B_{h_{s}} ∖ Ξ_{h_{s}} , with h_{s} −−−→^{q′,a,q} h_{s+1} and y_{s+1} = a, or a ≠ y_{s+1}^{−1} whence

q′ ∈ B_{h_{s}} ∩Ξ_{h_{s}} , with h_{s} −−−→^{q′,a,q} h_{s+1} and a = y_{s+1} . Hence a ∈ {t, t^{−1} }, h_{s} −−−→^{q′,a,q} h_{s+1}

with y_{s+1} = a, and there is a map η_{Δ′} from Δ′ to Ω_{h_{s}} and a vertex ν′ ∈ V (Δ′) such that η_{Δ′} (ν′) = q′. Thus, there is a lobe Δ adjacent to Δ′, a vertex ν ∈ V (Δ) and an isomorphism η_{Δ} from Δ to Ω_{h_{s+1}} such that η_{Δ} (ν) = q and η_{Δ} (R_{Δ} ) = Ξ_{h_{s+1}} and such that (ν′, a, ν) is a t-edge connecting Δ′ to Δ. Hence (α, z′′a, ν) is a path of the Schützenberger automaton and γ = Mγ′ is its associated geodesic type.

iii) Assume the transition function acts according to rule (3). Let γ′ = Nγ with N = (h_{s−1} , h_{s}, p, y_{s}, p′), where the n-th step of the derivation is (q′, Nγ, az′) ⊧ (q, γ, z′). In this case q′ ∈ Ξ_{h_{s}} and there is a path (p′, u, q′) of Ω_{h_{s}} for some u ∈ A(B) and a = y_{s}^{−1} . Accordingly (p, φ(u), q)((p, φ^{−1} (u), q)) is a path in Ω_{h_{s−1}} .

Since h_{s−1} −−−−−→^{p,a^{−1} ,p′} h_{s}, there are two lobes Δ and Δ′ of A(X̄, R_{HNN} ; w) and there exist two isomorphisms η_{Δ} from Δ to Ω_{h_{s−1}} and η_{Δ′} from Δ′ to Ω_{h_{s}} such that

η_{Δ}^{−1} (p) = r, η_{Δ′} (R_{Δ′} ) = Ξ_{h_{s}} , η_{Δ′}^{−1} (p′) = r′ and Δ −−−⟶^{r,a^{−1} ,r′} Δ′. Let η_{Δ′}^{−1} (q′) = ν′ and

η_{Δ}^{−1} (q) = v; hence (ν, a^{−1} , ν′) is a t-edge connecting Δ to Δ′ , and so (α, z, ν) is a path of A(X̄, R_{HNN} ; w) whose associated geodesic type is γ.

Let us prove the “if part”. Let π = (α, z, ν) be a path in A(X̄, R_{HNN} ; w) with ν ∈ V (Δ) for some lobe Δ of the Schützenberger automaton. We prove by induction on |z| that in P_{w} there is the computation (q_{0}, ⊥, zz′) ⊧^{|z|} (η_{Δ} (ν), σ, z′), where

σ = (h_{s−1} , h_{s}, p_{s−1} , y, q_{s}) …(0, h_{1}, p_{0}, y_{s}, q_{1})(0, 0, α, −, α)

with s ⩽ |z| is a geodesic type associated to the path π.

If |z| = 0, the statement clearly holds. Thus, assume that the statement holds for each word of length less than |z|. Let z′′∈ (X̄ ∪ X̄^{−1} )^{∗}, a ∈ X̄ ∪ X̄^{−1} such that z = z′′a and let π′ = (α, z′′, ν′) be a path with ν′ ∈ V (Δ′), where Δ′ is either an external lobe of the Schützenberger automaton or Ω_{0}. Let σ′ = (h_{j−1} , h_{j} , p_{j−1} , y_{j} , q_{j}) …(0, h_{1}, p_{0}, y_{1}, q_{0})(0, 0, α, −, α) be a geodesic type associated to π′. By induction hypothesis, in the automaton P_{w} there is a computation (q_{0}, ⊥, z′′az′) ⊧^{|z′′|} (η_{Δ′} (ν′), σ′, az′). Since the Schützenberger automaton is deterministic and π = (α, z, ν) is a path of the Schützenberger automaton, we get that (ν′, a, ν) is an edge of the Schützenberger automaton. We proceed considering the different possible positions of the vertex ν′.

i) Suppose that ν′ ∈ R_{Δ′} . If a ∉ {t, t^{−1} }, the edge (ν′, a, ν) ∈ E(Δ′), so taking Δ = Δ′ and applying first rule (1) to the configuration (η_{Δ′} (ν′), σ′, az′) we get (η_{Δ′} (ν′), σ′, az′) ⊧ (η_{Δ′} (ν), σ′, z′). Hence (q_{0}, ⊥, zz′) ⊧^{|z|} (η_{Δ} (ν), σ′, z′) where σ′ is a geodesic type associated to π. If a = y_{j}^{−1} , then we have to turn back to a yet visited lobe, thus let Δ be a lobe of type h_{j−1} , so using rule (3) we get (η_{Δ′} (ν′), σ′, az′) ⊧ (η_{Δ} (ν), σ′′, z′), where σ′′= (h_{j−1} , h_{j−2} , q_{j−1} , y_{j−2} , p_{j−2} ) … …(0, 0, α, −, α) is a geodesic type associated to π. Lastly, if a = y_{j} then q′ = η_{Δ′} (ν′) ∈ B_{h_{j}} and η_{Δ′} (Δ′) = Ω_{h_{j}} thus applying rule (2) we obtain the computation (η_{Δ′} (ν′), σ′, az′) ⊧ (η_{Δ} (ν), Mσ, z′) where Mσ with M = (h_{j} , h_{j+1} , q′, y_{j+1} , q) is the geodesic type associated to π.

ii) Assume ν′ ∉ R_{Δ′} . If η_{Δ′} (ν′) ∈ B_{h_{j}} ∖ Ξ_{h_{j}} and a = y_{j}; then we are entering a new lobe Δ of type say h_{j+1} , then applying rule (2) we obtain the computation (η_{Δ′} (ν′), σ′, az′) ⊧ (η_{Δ} (ν), Mσ′, z′) with

M = (h_{j} , h_{j+1} , η_{Δ′} (ν′), y, q_{h_{j+1}} )

Hence (q_{0}, ⊥, zz′) ⊧^{|z|} (η_{Δ} (ν), Mσ′, z′) and Mσ′ is a geodesic type associated to π. Finally if η_{Δ′} (ν′) ∉ B_{h_{j}} with a ∉ {t, t^{−1} } then Δ coincides with Δ′, whence using rule (1) we get (η_{Δ′} (ν′), σ′, az′) ⊧ (η_{Δ′} (ν), σ′, z′). Thus, (q_{0}, ⊥, zz′) ⊧^{|z|} (η_{Δ′} (ν), σ′, z′) where σ′ is a geodesic type associated to π. □

Theorem 3.3 gives a shorter alternative proof to the one presented in [14].

Theorem 3.4. The word problem in HNN-extensions of finite inverse semigroups is decidable.

Proof. Let w, w′ ∈ (X̄ ∪ X̄^{−1} )^{+} and let P_{w}, P_{w′} be the pushdown automata described in as in Definition 3.6 associated to w and w′, respectively. We know that wτ = w′τ if and only if w ∈ L[P_{w′}] and w′ ∈ L[P_{w}]. So the word problem reduces to a membership problem for deterministic context-free languages, and the membership problem for a deterministic context-free language can be solved in a linear time with respect to the length of the word to test [5]. □

We actually obtain a stronger result.

Corollary 3.2. Given an HNN-extension [S, A, B, φ] of a finite inverse semigroup S, if we assume that the presentation for S does not belong to the input, then there is a polynomial time algorithm that solves the word problem.

Proof. Since the membership problem for deterministic context free languages is linear in the length of a word [5], the algorithmic cost for the word problem is given by the construction of the grammar. Since the presentation for S does not belong to the input, the construction of all the external lobe types can be assumed as a constant cost. Thus, the effective cost is given by the construction of t-Core(w). With the notation introduced in Definition 2.2, the number of lobes of t-Core(w) is bounded from above by ∥w∥, whence the number of intersection vertices is also bounded from above by the quantity 2∥w∥. Furthermore, since the presentation of the semigroup S does not belong to the input, we may assume that the closure of each lobe has a constant cost. Hence, the number of operations to build t-Core(w) is given by the number of steps performed in Constructions 2–4 described in [14]. Since Construction 2 does not change the number of intersection vertices, every application of Construction 2(a) lowers the minimal idempotent read at an intersection vertex, and Construction 2(b) performs at most |S| quotients. Thus a single application of Construction 2 requires roughly at most 2∥w∥|S|^{2} steps, i.e., it has a linear cost O(∥w∥). Each elementary step of Construction 3 diminishes the number of lobes and it consists of a “cut and past” operation of the opuntoid graph followed by an application of Construction 2. Since this “cut and past” operation has a unitary cost, and each application diminishes the number of lobes (which are at most ∥w∥), we have that Construction 3 terminates after O(∥w∥^{2}) steps. Finally, it is not difficult to check that Construction 4 requires at most 2∥w∥|S| steps. Hence, the construction of t-Core(w) is done in O(∥w∥^{2}) steps, and this concludes the proof of the corollary. □

Acknowledgments

The authors acknowledge A. Cherubini for the fruitful discussions that greatly helped to improve the quality of the paper.

References

1. A. Cherubini, E. Rodaro, Amalgams vs Yamamura’s HNN-extensions of inverse semigroups, Algebra Colloq. 18(4) (2011), 647–657.

2. A. Cherubini, C. Nuccio, E. Rodaro, Multilinear equations in amalgams of finite inverse semigroups, Int. J. Algebra Comput. 21(1-2) (2011), 35–59.

3. A. Cherubini, C. Nuccio, E. Rodaro, Amalgams of finite inverse semigroups and deterministic context-free languages, Semigroup Forum 85(1) (2012), 129–146.

4. N. D. Gilbert, HNN-extensions of inverse semigroups and grupoid, J. Algebra 272 (2004), 27–45.

5. M. A. Harrison, Introduction to formal languages theory, Addison-Wesley. 1978.

6. G. Higman, B. H. Neumann, H. Neumann, Embedding theorems for groups, J. London Math. Soc. 26 (1949), 247–254.

7. J. M. Howie, Fundamentals of Semigroup Theory, Oxford Science Pubblications, 1995.

8. D. Janin, Toward a highter-dimensional string string theory for the modeling of computerized systems, Technical Report RR-1477-13, LaBRI, IPB, Université de Bordeaux, 2013.

9. J. Kellendonk, The local structure of tiling and their integer group of coinvariance, Commun. Math. Phys. 187 (1997), 115–157.

10. , Topological equivalence of tilings J. Math. Phys. 38 (1997), 1823–1842.

11. D. E. Muller P. E. Schupp, Context-free languages, groups, the theory of ends, second order logic, Theor. Comput. Sci. 37 (1985), 51–75.

12. W. D. Munn, Free inverse semigroups Proc. London Math. Soc. 29(3) (1974), 385–404.

13. E. Rodaro, Bicyclic subsemigroups in amalgams of finite inverse semigroups, Int. J. Algebra Comput. 20(1) (2010), 89–113.

14. E. Rodaro A. Cherubini, Decidability of the word problem in yamamura’s hnn extensions of finite inverse semigroups, Semigroup Forum 77(2) (2008), 163–186.

15. J. B. Stephen, Presentation of inverse monoids, J. Pure Appl. Algebra 198 (1990), 81–112.

16. A. Yamamura, HNN-extensions of inverse semigroups and applications, Internat. J. Algebra Comput. 7(5) (1997), 605–624.

Department of Mathematics (Received 11 11 2014) Politecnico di Milano “F. Brioschi”, Milan, Italy (Revised 25 02 2014)

 mohd.abu@polimi.it

Centro de Matemática, Universidade do Porto Porto, Portugal

 emanuele.rodaro@fc.up.pt