---
abstract: 'We show that the word problem for an amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ of inverse semigroups may be undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{R}$-classes and $\omega_1,\omega_2$ to be computable functions, interrupting a series of positive decidability results on the subject. This is achieved by encoding into an appropriate amalgam of inverse semigroups $2$-counter machines with sufficient universality, and relating the nature of certain [[Schützenberger ]{}]{}graphs to sequences of computations in the machine.'
author:
- |
    Emanuele Rodaro, Pedro V. Silva\
    Centro de Matemática, Faculdade de Ciências\
    Universidade do Porto, 4169-007 Porto, Portugal\
    {emanuele.rodaro,pvsilva}@fc.up.pt
bibliography:
- 'biblio.bib'
title: 'Amalgams of inverse semigroups and reversible two-counter machines.'
---

Introduction
============

If $S_1$, $S_2$ and $U$ are semigroups (groups) such that $U$ embeds into $S_1, S_2$ via two monomorphisms $\omega_1,\omega_2$ then $[S_1,S_2;U,\omega_1,\omega_2]$ is called an amalgam of semigroups (groups). The amalgamated free product $S_1*_U S_2$ associated with this amalgam in the category of semigroups (groups) is defined by the usual universal diagram. The amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ is said to be strongly embeddable in a semigroup (group) $S$ if there exist injective homomorphisms $\phi_i:
S_i{\rightarrow}S$ such that $\phi_1|_{\omega_1(U)}=\phi_2|_{\omega_2(U)}$ and $\phi_1(S_1)\cap \phi_2(S_2)=
\phi_1(\omega_1(U))= \phi_2(\omega_2(U))$. It is well known that every amalgam of groups embeds in a group (and hence in the amalgamated free product of the group amalgam) [@lyndon]. However there are many examples showing that in the category of semigroups not every amalgam of two semigroups is embeddable into a semigroup, see [@Kim; @Sapir]. On the other hand, T.E. Hall [@Hall2] showed that every amalgam of inverse semigroups (in the category of inverse semigroups) embeds in an inverse semigroup, and so in the corresponding amalgamated free product in the category of inverse semigroups. In general the class of embeddable amalgams of infinite semigroups behaves badly from the algorithmic point of view. In the paper [@BiMaMi], Birget, Margolis, and Meakin proved that the amalgamated free product of two finitely presented semigroups with solvable word problems and a nice common subsemigroup may have undecidable word problem. This result has been further strengthened by Sapir [@Sapir] by showing that an amalgamated free product of finite semigroups may have undecidable word problem. These results are in contrast to the situation for amalgamated free products of groups where the word problem is decidable (see [@lyndon]) assuming general nice conditions on the amalgam. The decidability result is a consequence of a normal form theorem for the free product with amalgamation of groups. A sort of normal form, but with a more geometric flavor, can be defined in the case of lower bounded or finite amalgams of inverse semigroups, see [@Ben; @Finite]. In [@Ben] Bennett showed that the word problem for lower bounded amalgam of inverse semigroups has decidable word problem, this is achieved by giving an ordered way to build the [[Schützenberger ]{}]{}automata in such structure. Taking inspiration from Bennett’s paper, Cherubini, Meakin and Piochi in [@Finite], quite in contrast with Sapir’s result, showed that the word problem for any amalgamated free product of finite inverse semigroups is decidable in the category of inverse semigroups. As already pointed out, this result has been achieved adapting nontrivially the work of Bennett to the finite case to obtain a sort of geometric normal form of a word $w$, called by the authors $Core(w)$. This fact, along with other lifting properties of [[Schützenberger ]{}]{}automata for amalgams of finite inverse semigroups, gave rise to a series of papers [@ChNuRo; @RoByci; @RoChe] in the decidability direction. Although these clues can push toward a decidability result for amalgams of inverse semigroups with nice conditions, in this paper we give a result which goes in the opposite direction:

The word problem for an amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ of inverse semigroups may be undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{R}$-classes and $\omega_1,\omega_2$ to be computable functions.

This is achieved by encoding into an appropriate amalgam of inverse semigroups a $2$-counter machine having the right property, but still general enough to hold universality properties with respect to Turing machines. Then we show how the nature of certain [[Schützenberger ]{}]{}graphs relates to sequences of computations in the machine.

Inverse semigroups
==================

A semigroup $S$ is said to be [*inverse*]{} if, for each element $a \in S$, there is a unique element $a^{-1} \in S$ such that $a = a a^{-1} a$ and $a^{-1} = a^{-1} a a^{-1}$. A consequence of the definition is that idempotents commute in any inverse semigroup. Moreover, a natural partial order can be defined on $S$ by $a \leq b$ if and only if $a = e b$ for some idempotent $e$ of $S$.

Inverse semigroups may be regarded as semigroups of partial one-to-one transformations closed under inversion, so they arise very naturally in several areas of mathematics. More recently, also computer scientists have been paying attention to inverse semigroups for different reasons. First, the inverse of an element in an inverse semigroup can be seen as the “undo” of the action represented by the element. Second, algorithmic problems for inverse semigroups have received considerable attention in the literature during the past 30-35 years and in the cases where such problems are decidable, the analysis of the complexity of these algorithms is a quite natural issue.

The natural geometric framework to deal with algorithmic problems in an inverse semigroup generated by $X$ is the class of *inverse $X$-graphs*. Write ${\widetilde}{X} = X\cup X^{-1}$, where $X^{-1}=\{x^{-1}:x\in
X\}$ is a set of formal inverses of $X$. We can extend $\cdot^{-1}$ to an involution on ${\widetilde}{X}^*$ through $(x{^{-1}}){^{-1}}= x$ $(x \in X)$ and $(uv){^{-1}}= v{^{-1}}u{^{-1}}$ $(u,v \in {\widetilde}{X}^*)$.

An inverse $X$-graph is a pair $\Gamma = (V,E)$ where $V = V(\Gamma)$ denotes the vertex set and $E = E(\Gamma) \subseteq V \times X \times V$ the edge set. We say that $\Gamma$ is:

-   [*involutive*]{} if $(p,x,q) \in E \Rightarrow (q,x{^{-1}},p) \in E$ for all $p,q \in V$ and $x \in {\widetilde}{X}$;

-   [*deterministic*]{} if $(p,x,q), (p,x,r) \in E \Rightarrow q = r$ for all $p,q,r \in V$ and $x \in {\widetilde}{X}$;

-   [*connected*]{} if any two vertices can be connected through a path in $\Gamma$;

-   [*inverse*]{} if it is involutive, deterministic and connected.

An *inverse $X$-automaton* is a triple $\mathcal{A} = (\alpha,\Gamma,\beta)$ where $\Gamma$ is an inverse $X$-graph and $\alpha,\beta\in V(\Gamma)$ are respectively the initial and final state of the automaton.

The free inverse semigroup on a set $X$, denoted by $FIS(X)$, is the quotient of the free semigroup ${\widetilde}{X}^+$ by the least congruence $\rho$ that makes the resulting quotient semigroup inverse (Vagner congruence). Its elements may be seen as finite birooted inverse $X$-trees usually known as [*Munn trees*]{} (see [@munn]).

An inverse semigroup presentation is a formal expression of the form Inv${\langle}X \mid R {\rangle}$, where $R\subseteq {\widetilde}{X}^+ \times
{\widetilde}{X}^+$. The presentation is finite if both $X$ and $R$ are finite. The inverse semigroup defined by this presentation is the quotient of ${\widetilde}{X}^+$ by the congruence $\tau$ generated by $\rho \cup
R$. We often represent the elements of $R$ as equalities of the form $w_1=w_2$.

In the paper [@Steph], Stephen has extended the notion of Munn tree introducing the Schützenberger automaton $\mathcal{A}(X,R;w)$ for a word $w \in {\widetilde}{A}^+$ relative to the presentation Inv${\langle}X\mid R{\rangle}$ of $S$. The underlying graphs $S\Gamma(X,R;w)$ of these automata are the strongly connected components of the Cayley graph of the presentation, which has $S$ as vertex set and edges $(s,x,s(x\tau))$ $(s \in S, x \in {\widetilde}{X}$. More precisely, $S\Gamma(X,R;w)$ is the restriction of this Cayley graph to the Green $\mathcal{R}$-class of $w\tau$ in $S$. It turns out that $S\Gamma
(X,R;w)$ is an inverse $X$-graph and we can now define the [[Schützenberger ]{}]{}automaton $$\mathcal{A}(X,T;w) = ((ww^{-1})\tau,S\Gamma (X,T;w),w\tau).$$ The importance of these automata stems from the fact that any two words $w,
w' \in {\widetilde}{X}^+$, represent the same element of $S$ if and only if $\mathcal{A}(X,R;w) = \mathcal{A}(X,R;w')$, equivalent also to $$w \in L(\mathcal{A}(X,R;w')) \quad \mbox{and} \quad  w' \in
L(\mathcal{A}(X,R;w)).$$ Hence [[Schützenberger ]{}]{}automata are crucial for dealing with algorithmic problems. In [@Steph] it is also provided an iterative procedure for approximating the [[Schützenberger ]{}]{}automaton relative to a given presentation Inv$\langle X\mid R\rangle$ of a word $w\in {\widetilde}{X}^+$ via two operations, $R$-*expansions* and *foldings*. Let $\mathcal{A}$ be a finite inverse $X$-automaton. An $R$-expansion of $\mathcal{A}$ consists in adding a nonexisting path $p \mapright{r'} q$ to $\mathcal{A}$ (and the corresponding inverse edges) whenever $p \mapright{r} q$ is a path in $\mathcal{A}$ but no path $p \mapright{r'} q$ is present $(r,r')\in R\cup R^{-1}$. A folding consists in identifying two edges starting at the same vertex and labeled by the same letter of the alphabet ${\widetilde}{X}$. We say that $\mathcal{A}$ is $R$-*closed* if no $R$-expansion can be performed. The iterative sistematic application of $R$-expansions (considering all possible instances simultaneously) and complete folding to the Munn tree of a word $w\in
{\widetilde}{X}^+$ (obtained itself as the complete folding of the linear automaton $\to \bullet
\mapright{w} \bullet \to$) produces a (possibly infinite) sequence of finite inverse $X$-automata $$\mathcal{A}_1{\rightarrow}\mathcal{A}_2{\rightarrow}\ldots{\rightarrow}\mathcal{A}_j{\rightarrow}\ldots$$ whose colimit is $\mathcal{A}(X,R;w)$. This colimit procedure can in fact be applied starting from any finite inverse $X$-automaton $\mathcal{A}$, producing as its colimit the $R$-*closure* of $\mathcal{A}$, i.e., the smallest (with respect to language) $R$-closed $X$-inverse automaton recognizing all words in $L(\mathcal{A})$ (see [@Steph98]). Any finite inverse $X$-automaton obtained from the Munn tree of $w$ by $R$-expansions and foldings is said to be a [*finite approximation*]{} of $\mathcal{A}(X,R;w)$.

We close this section by fixing some notation for amalgams to be preserved through the whole paper. Let $S_i = {\widetilde}{X_i}^+ / \tau_i$ be the inverse semigroup defined by Inv$\langle X_i\mid R_i\rangle$ for $i=1,2$ with $X_1\cap
X_2=\emptyset$. Let $\lambda_i:S_i{\rightarrow}{\widetilde}{X_i}^+$ be a map such that, for each $s\in S_i$, $(\lambda_i(s))\tau_i =s$ $(i = 1,2)$. Finally, let $U$ be an inverse semigroup and $\omega_i:U \to S_i$ a monomorphism for $i = 1,2$. The [*free product with amalgamation*]{} $S_1*_US_2$ associated to the amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ is the inverse semigroup presented by $$Inv{\langle}X_1\cup X_2 \mid R_1\cup R_2\cup R_3{\rangle},$$ where $R_3=\{(\lambda_1(\omega_1(u)),\lambda_2(\omega_2(u)))\mid u\in
U\}$.

Counter machines {#sec:introduction counter machine}
================

A $k$-counter machine (for short, $CM(k)$) is a system $$\mathcal{M}=(Q,\delta,\iota,f)$$ where $k$ is the number of tapes, $Q$ is the nonempty finite set of internal states, $\iota\in Q$ is the initial state, and $f\in Q$ is the final (halting) state. The machine $\mathcal{M}$ uses $A = \{\perp,a\}$ as a tape alphabet ($\perp$ is a blank symbol), $\delta$ is a move relation which is a subset of $(Q \times \{1,\ldots,k\} \times A \times Q)\cup
  (Q \times\{1,\ldots,k\} \times D \times Q)$ where $D = \{ -,0,+\}$ and the symbols $-,0,+$ denote respectively left-shift, no-shift, and right-shift of a head of the machine. Tapes are one-way (rightward) infinite. The leftmost squares of the tapes contain the blank symbol $\perp$, and all the other squares contain the symbol $a$.

Each element of $\delta$ is thus a quadruple of one of the two forms: $$(q,i,s,q'),\;(q,i,d,q')$$ where $q,q'\in Q$, $i\in\{1,\ldots,k\}$, $s\in A$ and $d\in D$. A quadruple of the form $(q,i,s,q')$ means that if $\mathcal{M}$ is in the state $q$ and the $i$th-head is reading the symbol $s$ then the machine changes its state into $q'$. This instruction is used to test whether the content of a counter is zero (the head is reading the symbol $\perp$) or positive (the head is reading a square with symbol $a$). We call this kind of instructions *test instructions*. On the other hand an instruction $(q,i,d,q')$ means that if $\mathcal{M}$ is in the state $q$ then:

-   it shifts the $i$th-head one cell to the right if $d = +$,

-   it shifts the $i$th-head one cell to the left if $d = -$,

-   it keeps the $i$th-head at the same cell if $d = 0$,

and changes its state into $q'$. The evolution of a $CM(k)$ $\mathcal{M}$ can be followed through instantaneous descriptions of the machine:

An instantaneous description (for short, ID) of a $CM(k)$ $\mathcal{M}=(Q,\delta,\iota,f)$ is a $(k+1)$-tuple $(q,n_1,\ldots,
n_k)\in Q\times\mathbb{N}^k$. It represents that $\mathcal{M}$ is in state $q$ and the $i$th-head is in position $n_i$ for $i=1,\ldots,k$, where we assume the position of the leftmost square of a tape to be $0$. The transition relation $\vdash_{\mathcal{M}}$ is defined as follows: $$(q,n_l,\ldots, n_{i-1},n_i,n_{i+1}\ldots,
n_k)\vdash_{\mathcal{M}}(q',n_l,\ldots, n_{i-1},n_i',n_{i+1}\ldots,
n_k)$$ holds if one of the following conditions is satisfied:

1.  $(q,i,\perp,q')\in\delta$ and $n_i=n_i'=0$.

2.  $(q,i,a,q')\in\delta$ and $n_i=n_i'>0$.

3.  $(q,i,-,q')\in\delta$ and $n_i-1=n_i'$.

4.  $(q,i,0,q')\in\delta$ and $n_i=n_i'$.

5.  $(q,i,+,q')\in\delta$ and $n_i+1=n_i'$.

We denote the reflexive and transitive closure of $\vdash_{\mathcal{M}}$ by $\vdash_{\mathcal{M}}^*$ and the $n$-step transition relation by $\vdash_{\mathcal{M}}^n$.

Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a $CM(k)$. We say that the $k$-tuple $(n_1,\ldots,n_k) \in \mathbb{N}^k$ is accepted by $\mathcal{M}$ if $$(\iota,n_1,\ldots,n_k) \vdash_{\mathcal{M}}^* (f,n'_1,\ldots,n'_k)$$ for some $(n'_1,\ldots,n'_k) \in \mathbb{N}^k$.

Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a $CM(k)$ and $\alpha_i=(p_i,j_i,x_i,p_i')$ with $i\in\{1,2\}$ be two distinct quadruples in $\delta$. We say that $\alpha_1,\alpha_2$ overlap in domain if $$p_1=p_2\wedge (j_1\neq j_2\vee x_1=x_2\vee x_1\in D\vee x_2\in D).$$ We say that $\alpha_1,\alpha_2$ overlap in range if $$p_1'=p_2'\wedge (i_1\neq i_2\vee x_1=x_2\vee x_1\in D\vee x_2\in D).$$

A quadruple $\alpha \in \delta$ is called *deterministic* (*reversible* respectively) if there is no other quadruple in $\delta$ which overlaps in domain (range) with $\alpha$. The machine $\mathcal{M}$ is called *deterministic* (*reversible* respectively) if every quadruple in $\delta$ is deterministic (reversible). It is clear from the definitions that every ID of a deterministic (reversible, respectively) $CM(k)$ has at most one ID that immediately follows (precedes) it in some computation. In this paper we focalize on reversible deterministic 2-counter machines because of their universality property. Indeed, the following Theorem holds:

[@Morita]\[theo:morita\] For any deterministic Turing machine $\mathcal{T}$ there is a deterministic reversible $CM(2)$ $\mathcal{M}$ that simulates $\mathcal{T}$.

A 2-counter machine $\mathcal{M}=(Q,\delta,\iota,f)$ can be sketched as a labeled graph $\mathrsfs{G}(\mathcal{M})$ with set of vertices $Q$ and labeled edges $\delta$ where we picture $(q_1,i,h,q_2)\in\delta$ as an arrow from $q_1$ to $q_2$ labelled by $i,h$ with $i\in\{1,2\}$ and $h\in\{a,\perp,+,0,-\}$. It is clear from the definition that if $\mathcal{M}$ is deterministic then the only case where a vertex $q$ of $\mathrsfs{G}(\mathcal{M})$ may have two outgoing edges is when we have tests instructions (Fig. \[fig1\]), i.e. $(q,i,a,q_1),(q,i,\perp,q_2)$ are two edges of $\mathrsfs{G}(\mathcal{M})$ with $i\in\{1,2\}$. Dually, if $\mathcal{M}$ is reversible then the only case where a vertex $q$ of $\mathrsfs{G}(\mathcal{M})$ may have two ingoing edges is when they are of the form $(q_1,i,a,q),(q_2,i,\perp,q)$ for some $i\in\{1,2\}$ (Fig. \[fig1\]).

![The deterministic case (on the left) and the reversible case (on the right).[]{data-label="fig1"}](detrev.eps)

For our purpose we are interested in deterministic 2-counter machines with the following property.

Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a deterministic $CM(2)$. We say that $\mathcal{M}$ is alternating if, for all pairs of different instructions $(q,i,h,q'),(q',j,h',q'')\in\delta$, we have $j= 3-i$.

We can prove the following proposition:

\[alter\] Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a deterministic reversible $CM(2)$. Then there is a deterministic reversible and alternating $CM(2)$ $\mathcal{M}'$ that simulates $\mathcal{M}$.

What we actually do is to add some dummy states whenever there occur two instructions $(p,i,h,q),(q,i,x_1,r_1)\in\delta$. Formally $\mathcal{M}'=(Q',\delta',\iota,f)$ is obtained applying iteratively the following procedure. Whenever $(p,i,h,q)$, $(q,i,x_1,r_1)\in\delta$, we substitute in $\delta$ all the instructions $(q,i,x_k,r_k)\in\delta$ (at most two since $\mathcal{M}$ is deterministic) by the pairs of instructions $$(q,3-i,0,q_{(q,i,x_k,r_k)}), (q_{(q,i,x_k,r_k)},i,x_k,r_k)$$ where $q_{(q,i,x_k,r_k)}$ is the dummy state added. It is easy to see that the obtained $CM(2)$ $\mathcal{M}'$ is an alternating deterministic and reversible $CM(2)$ that simulates $\mathcal{M}$.

Note that we can always replace an instruction $(p,i,0,q)$ by the couple of instructions $(p,i,a,q), (p,i,\perp,q)$ and on doing so the $CM(2)$ remains deterministic, reversible and alternating. Therefore, we shall assume henceforth that our $CM(2)$ have no instructions of type $(p,i,0,q)$. A $CM(2)$ which is deterministic, reversible, alternating and has no instructions of the form type $(p,i,0,q)$ is said to be [*normalized*]{}. Taking in particular a universal Turing machine in Theorem \[theo:morita\] and being undecidable whether or not a universal Turing machine can accept a given input, it follows that there exists a $CM(2)$ $\mathcal{M}_0$ such that it is undecidable whether or not a given $(m,n) \in \mathbb{N}^2$ is accepted by $\mathcal{M}_0$. Therefore by Proposition \[alter\] we have the following Corollary.

\[cor:universal\] There exists a normalized $CM(2)$ $\mathcal{M}^*$ such that it is undecidable whether or not a given $(m,n) \in \mathbb{N}^2$ is accepted by $\mathcal{M}^*$.

Amalgam associated to a $2$-counter machine
===========================================

In this section we associate an amalgam $[S_1,S_2;U]$ of inverse semigroups to a deterministic reversible alternating $2$-counter machine $$\mathcal{M}=(Q,\delta,\iota,f)$$ The rough idea is depicted in Fig. \[fig2\]: we encode the two tapes of the machine $\mathcal{M}$ by two inverse semigroups $S_1, S_2$ and the control of $\mathcal{M}$ is handled through a common inverse subsemigroup $U$.

![The rough idea of the encoding.[]{data-label="fig2"}](schematic.eps)

\
We start by associating to $\mathcal{M}$ two inverse semigroups $S_1, S_2$, representing the two tapes, called respectively the *left tape inverse semigroup* and the *right tape inverse semigroup* of $\mathcal{M}$.

\[def:tape inverse semigroup\] Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a deterministic reversible alternating $2$-counter machine. The left and right tape inverse semigroups associated to $\mathcal{M}$ are the inverse semigroups $S_i$ $(i= 1,2)$ presented by Inv${\langle}X_i \mid \mathcal{T}_i{\rangle}$, where: $$X_i=\{\perp_i, a_i,t_i\} \cup \{q_i:q\in Q\},$$ $$\mathcal{T}_i=\mathcal{T}_i^c\cup\mathcal{T}_i^t\cup\mathcal{T}_i^w
\cup\mathcal{T}_i^e\cup\mathcal{T}_i^f$$ and:

-   $\mathcal{T}_i^c$ are the commuting relations, used to keep track of the instantaneous description of the machine;

-   $\mathcal{T}_i^t$ are the test relations (corresponding to the test instructions);

-   $\mathcal{T}_i^{w}$ are the writing relations (corresponding to instructions that move the head of the $i$th tape to the right);

-   $\mathcal{T}_i^{e}$ are the erasing relations (corresponding to instructions that move the head of the $i$th tape to the left);

-   $\mathcal{T}_i^f$ are the finiteness relations (designed to enforce some finiteness properties on the semigroup $S_i$).

More precisely the relations are defined in the following way:

-   $\mathcal{T}_i^d$ consists of all the relations of the form $t_ix
    =xt_i$, for $x\in\{a_i,a_i{^{-1}},\perp_i,\perp_i{^{-1}}\}$ and $i = 1,2$.

-   For each test instruction $(p,1,s,q)\in\delta$ $(s\in A)$, we add to $\mathcal{T}^t_1$ the relation $sp_1=st_1q_1t_1^{-1}$.

-   For each test instruction $(p,2,s,q)\in\delta$ $(s\in A)$, we add to $\mathcal{T}^t_2$ the relation $p_2s=t_2q_2t_2^{-1}s$.

-   For each right move instruction $(p,1,+,q)\in\delta$, we add to $\mathcal{T}^w_1$ the relations $sp_1=st_1a_1q_1t_1^{-1}$ $(s\in A)$.

-   For each right move instruction $(p,2,+,q)\in\delta$, we add to $\mathcal{T}^w_2$ the relations $p_2s=t_2q_2a_2t_2^{-1}s$ $(s\in A)$.

-   For each left move instruction $(p,1,-,q)\in\delta$, we add to $\mathcal{T}^w_1$ the relations $sa_1p_1=st_1q_1t_1^{-1}$ $(s\in A)$.

-   For each left move instruction $(p,2,-,q)\in\delta$, we add to $\mathcal{T}^w_2$ the relations $p_2a_2s=t_2q_2t_2^{-1}s$ $(s\in A)$.

-   The set of relations $\mathcal{T}_1^f$ is formed by $$\begin{array}{l}
    f_1x = xf_1 = f_1 \quad (x \in {\widetilde}{X_1}),\\
    q_1x = f_1  \quad (q \in Q, \; x \in {\widetilde}{X_1}\setminus \{
    q_1{^{-1}}\}),\\
    p_1{^{-1}}q_1 = f_1 \quad (p,q \in Q \mbox{ distinct}),\\
    a_1\perp_1{^{-1}}= \perp_1{^{-1}}a_1 = f_1.
    \end{array}$$

-   The set of relations $\mathcal{T}_2^f$ is formed by $$\begin{array}{l}
    f_2x = xf_2 = f_2 \quad (x \in {\widetilde}{X_2}),\\
    xq_2 = f_2  \quad (q \in Q, \; x \in {\widetilde}{X_2}\setminus \{
    q_2{^{-1}}\}),\\
    p_2 q_2{^{-1}}= f_2 \quad (p,q \in Q \mbox{ distinct}),\\
    a_2\perp_2{^{-1}}= \perp_2{^{-1}}a_2 = f_2.
    \end{array}$$

\[rem:one to one encoding\] Clearly $f_i$ is a zero element for the inverse semigroup $S_i$. Note also that in cases (iv)-(vii) we have added two relations for a single move to force $a_i$ or $\perp_i$ to be present on both sides of each relation. This is done for reasons which will become clear when we shall introduce the inverse semigroup $U$. Indeed, this way the embeddability of $U$ into the tape inverse semigroups is verified since we avoid any nontrivial relations having only generators of $U$ in one side. On the other hand, each test instruction gives birth to a single relation (cases (ii)-(iii)).

We associate to $\mathcal{M}$ another inverse semigroup $U$ which represents its control unit:

\[def:core inverse semigroup\] Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a deterministic reversible alternating $2$-counter machine. The core inverse semigroup of $\mathcal{M}$ is the inverse semigroup $U$ presented by Inv${\langle}X_U\mid \mathcal{T}_U{\rangle}$, where $X_U = Q \cup \{ t \}$ and the set of relations $\mathcal{T}_U$ is formed by $$\begin{array}{l}
fx = xf = f \quad (x \in {\widetilde}{X_U}),\\
pq = f  \quad (p,q \in Q),\\
pq{^{-1}}= p{^{-1}}q = f \quad (p,q \in Q \mbox{ distinct}).
\end{array}$$

Similarly to the previous cases, $U$ has a zero $f$. With the notation of Definitions \[def:tape inverse semigroup\] and \[def:core inverse semigroup\] we can prove the following result:

\[prop:embedding property\] Let $\mathcal{M}$ be a deterministic reversible alternating $2$-counter machine and let $S_1,S_2,U$ be respectively the left-right tape inverse semigroups and the core inverse semigroup of $\mathcal{M}$. The map $\omega_i$ defined by $$\omega_i(t)=t_i,\;\omega_i(q)=q_i \; (q \in Q)$$ can be extended to a monomorphism $\omega_i:U\hookrightarrow S_i$ for $i=1,2$.

Let $u,v \in {\widetilde}{X_U}^+$ and assume that $\omega_i(u) = \omega_i(v)$ in $S_i$. Suppose first that $\omega_i(u)$ is not the zero element of $S_i$. Then we are forbidden to use relations from $\mathcal{T}_i^f$ to transform $\omega_i(u)$ into $\omega_i(v)$. Since all the other relations of $\mathcal{T}_i$ involve $a_i$ or $\perp_i$, it follows that $\omega_i(v)$ must actually equal $\omega_i(u)$ in the free inverse semigroup over $X_U$, and so we definitely have $u = v$ in $U$. Hence we may assume that $\omega_i(u) = f_i$ in $S_i$. But the unique relations in $\mathcal{T}_i$ where neither $a_i$ nor $\perp_i$ occur are precisely (up to subscript $i$) those of $\mathcal{T}_U$, hence we may apply one of the latter relations to $u$ (possibly after some Vagner congruence relations) to get an occurrence of $f$. Thus $u = f$ in $U$. Similarly, also $v = f$ in $U$ and so $u = v$ holds in $U$ as required.

In view of Proposition \[prop:embedding property\] we can associate to a deterministic reversible alternating $2$-counter machine an amalgam:

\[defn:amalgam associate to M\] Let $\mathcal{M}=(Q,\delta,\iota,f)$ be a deterministic reversible alternating $2$-counter machine. The amalgam of inverse semigroups associated to $\mathcal{M}$ is the $5$-tuple $[S_1,S_2;U,\omega_1,\omega_2]$ where $S_1, S_2$ are the left-right tape inverse semigroups of $\mathcal{M}$, $U$ is the core inverse semigroup of $\mathcal{M}$ and $\omega_i:U\hookrightarrow S_i$ are the embeddings of Proposition \[prop:embedding property\]. In this way the free product with amalgamation of the amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ associated to $\mathcal{M}$ can be presented by $$\mbox{Inv}
  {\langle}X_1\cup X_2\mid \mathcal{T}_1\cup\mathcal{T}_2\cup\mathcal{T}_3{\rangle}$$ where $$\mathcal{T}_3=\{(q_1,q_2):q\in Q\}\cup\{(t_1,t_2)\}$$

The left-right tape inverse semigroups $S_i$ have the following important property:

\[finiter\] Let $\mathcal{M}$ be a deterministic reversible alternating $2$-counter machine and let $S_1,S_2$ be respectively the left-right tape inverse semigroups of $\mathcal{M}$. Then the Green $\mathcal{R}$-classes of $S_i$ are finite for $i = 1,2$.

First of all, let $\mathcal{M}'$ be the machine $\mathcal{M}$ with counters 1 and 2 reversed. It is easy to check that $t_2 \to t_1{^{-1}}$, $q_2 \to q_1$, $a_2 \to a_1$, $\perp_2 \to \perp_1$ induces an isomorphism from $S_2$ onto the dual of $S'_1$, hence it suffices to show that the Green $\mathcal{R}$-classes of $S_1$ are finite. This is of course equivalent to say that the [[Schützenberger ]{}]{}graphs of $S_1$ are finite. To simplify notation, we drop all the subscripts 1 in $S_1$, $\mathcal{T}_1$, $X_1$ and its letters.

Let $w \in {\widetilde}{X}^+$ and let $(\mathcal{A}_k)_k$ be the Stephen’s sequence whose colimit is $\mathcal{A}(X,\mathcal{T};w)$. We can of course assume that $w$ does not represent the zero element of $S$, which is the single element of its $\mathcal{R}$-class. Let $m_0$ be the total number of edges labeled by letters of $Q$ in the Munn tree of $w$. We claim that there are at most $m_0$ expansions in the sequence $(\mathcal{A}_k)_k$ featuring edges labeled by elements of $Q$ ($Q$-edges).

Indeed, let $Q'$ consist of all $p \in Q$ such that there exists some instruction $(p,1,\ldots, \ldots) \in \delta$, and let $Q''$ consist of all $q \in
Q$ such that there exists some instruction $(\ldots,1,\ldots, q) \in
\delta$. Since $\mathcal{M}$ is alternating, we have $Q' \cap Q'' =
\emptyset$. Moreover, since $\mathcal{M}$ is deterministic (respectively reversible), each element of $Q'$ (respectively $Q''$) can feature a unique expansion: this is true for relations of type (ii), which are the unique outcome of a test instruction, and even if two test instructions $(p,1,a,q), (p,1,\perp,r)$ are present in $\delta$, the corresponding relations can never be used simultaneously for the same $p$-edge in view of the forbidden relations $a\perp{^{-1}}= f$ (we are assuming that $w \neq f$ in $S$). Similarly, the same $Q$-edge cannot feature two expansions involving relations of type (iv) or (vi), where application of both relations arising from a single instruction would ensure the appearance of a factor $a\perp{^{-1}}$. And of course, the relations of (viii) are altogether forbidden since $w
\neq f$ in $S$.

Therefore there exists some $m_1 \in \mathbb{N}$ such that all expansions and foldings involving $Q$-edges in $(\mathcal{A}_k)_k$ have taken place before we reach $\mathcal{A}_{m_1}$.

Given $Y \subseteq X$, let $\sigma_Y:{\widetilde}{X}^* \to \mathbb{Z}$ be the homomorphism defined by $$\sigma_Y(x) = \left\{
\begin{array}{rl}
1&\mbox{ if }x \in Y\\
-1&\mbox{ if }x \in Y{^{-1}}\\
0&\mbox{ if }x \in {\widetilde}{X} \setminus {\widetilde}{Y}
\end{array}
\right.$$ We claim that $$\label{tloop}
\mbox{If $u$ labels a loop in some $\mathcal{A}_k$, then $\sigma_t(u) =
  0$.}$$ Indeed, this holds trivially for the Munn tree $\mathcal{A}_1$. Since $\sigma_t(r) = \sigma_t(r')$ for every $(r,r') \in \mathcal{T} \setminus
\mathcal{T}^f$, this property is inherited through expansions in the Stephen’s sequence (expansions featuring relations of $\mathcal{T}^f$ are forbidden since $w \neq f$ in $S$). Finally, the property is inherited through foldings as well: if $\mathcal{A}'$ is obtained from $\mathcal{A}$ folding two edges of label $x$, then every loop in $\mathcal{A}'$ can be lifted to a loop in $\mathcal{A}$ by successively inserting factors of the form $x{^{-1}}x$. Therefore (\[tloop\]) holds. We complete now the proof of our proposition by showing that the $\mathcal{T}^c$-closure of $\mathcal{A}_{m_1}$ is finite. Note that the $\mathcal{T}^c$-closure of $\mathcal{A}_{m_1}$ is also its $\mathcal{T}$-closure: we cannot use relations of $\mathcal{T}^t \cup
\mathcal{T}^w \cup \mathcal{T}^e$ by definition of $m_1$, and we cannot use relations of $\mathcal{T}^f$ since $u \neq f$ in $S$.

Let $C_1, \ldots, C_{\ell}$ be the connected components of the automaton obtained by removing all $Q$-edges from $\mathcal{A}_{m_1}$ (the $c$-components). Clearly, performing $\mathcal{T}^c$-expansions cannot merge $c$-components, neither can folding edges with label in ${\widetilde}{A \cup t}$ (and folding of $Q$-edges will not occur after $\mathcal{A}_{m_1}$. Therefore we only need to prove that the $\mathcal{T}^c$-closure of a $c$-component $C_j$ is finite for $j = 1,\ldots, \ell$. In view of (\[tloop\]), it is enough to prove that

-   If $\mathcal{A}$ is a finite inverse ${\widetilde}{A\cup t}$-automaton where every $u \in {\widetilde}{A\cup t}^*$ labelling a loop satisfies $\sigma_t(u) =
    0$, then the $\mathcal{T}^c$-closure $\mathcal{B}$ of $\mathcal{A}$ is finite.

Let $n = |V(\mathcal{A})|$ and suppose that there is a path $i \mapright{v} j$ in $\mathcal{A}$ with $|\sigma_t(v)| \geq n$. We may assume that $v$ is shortest possible. Since $|v| \geq n$, the path $i \mapright{v} j$ must contain a loop, hence we may factor it as $$i \mapright{v_1} i_1 \mapright{u} i_1 \mapright{v_2} j$$ with $v = v_1uv_2$ and $u \neq 1$. Now $\sigma_t(u) = 0$ yields $\sigma_t(v_1v_2) = \sigma_t(u)$ and so $v_1v_2$ is a shorter alternative to $u$, a contradiction. Thus $|\sigma_t(v)| < n$ whenever $v$ labels a path in $\mathcal{A}$. We claim that also $$\label{tbound}
|\sigma_t(v)| < n \mbox{ whenever $v$ labels a path in } \mathcal{B}.$$ Indeed, it suffices to remark that this property is inherited through $\mathcal{T}^c$-expansions and foldings, using the same argument in the proof of (\[tloop\]).

Assume that $i_1, \ldots, i_r$ are the vertices of $\mathcal{B}$ corresponding to the starting points of edges labelled by $a$ or $\perp$ in $\mathcal{A}$. We claim that if $i \mapright{s} j$ is an edge of $\mathcal{B}$ with $s \in A$, then there exists a path $i_k
\mapright{v} i$ in $\mathcal{B}$ for some $k \in \{ 1, \ldots, r\}$ and $v \in {\widetilde}{t}^*$. Once again, it suffices to check that this property is inherited through $\mathcal{T}^c$-expansions and foldings, a quite trivial observation. Since $\mathcal{B}$ is inverse, we may in fact assume that $v \in t^* \cup (t{^{-1}})^*$. In view of (\[tbound\]), it follows that there are only finitely many $A$-edges in $\mathcal{B}$, and again by (\[tbound\]), the number of $t$-edges must also be finite. Therefore (P) holds and the proposition is proved.

Undecidability of the word problem for amalgams
===============================================

In this section we prove that the word problem for an amalgam$[S_1,S_2;U,\omega_1,\omega_2]$ of inverse semigroups is undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{R}$-classes and $\omega_1,\omega_2$ to be computable functions. The idea is to relate the computation of a deterministic reversible alternating $2$-counter machine with the [[Schützenberger ]{}]{}graphs of the associated amalgam.

We fix now a normalized $CM(2)$ $\mathcal{M} = (Q,\delta,\iota,f)$ and consider the semigroup $S$ defined by the associated amalgam $[S_1,S_2;U,\omega_1,\omega_2]$. Write $X = X_1\cup X_2$ and $\mathcal{T} = \mathcal{T}_1\cup\mathcal{T}_2\cup\mathcal{T}_3$. Clearly $f_1$ and $f_2$ represent both the zero of $S$. Let $(m,n) \in \mathbb{N}^2$ and write $w_{m,n} =
\perp_1a_1^m\iota_1 a_2^n\perp_2$. Suppose that $$(\iota,m,n) = (q^{(0)},m_0,n_0) \vdash_{\mathcal{M}} \ldots
\vdash_{\mathcal{M}} (q^{(k)},m_k,n_k).$$ Since $\mathcal{M}$ is deterministic, there is at most one such sequence of a given length starting with $(\iota,m,n)$. Write $m'_k = \max\{ m_0, \ldots, m_k\}$, $n'_k = \max\{ n_0, \ldots,
n_k\}$. We define a finite inverse $X$-automaton $\mathcal{B}_{m,n}^{(k)}$ as follows (describing only the edges with positive label):

-   The vertices are of the form $c_{i,j}$ and $d_{i,\ell}$ for $i =
    0,\ldots,k$ and $j = 0,\ldots,m'_k+1$ and $\ell = 0,\ldots,n'_k+1$.

-   $c_{0,0}$ is initial and $d_{0,0}$ is final.

-   There exist edges $c_{i-1,j} \longmapright{t_1,t_2} c_{i,j}$ for all $i =
    1,\ldots,k$ and $j = 0,\ldots,m'_k+1$.

-   There exist edges $d_{i-1,\ell} \longmapright{t_1,t_2} d_{i,\ell}$ for all $i =
    1,\ldots,k$ and $\ell = 0,\ldots,n'_k+1$.

-   There exist edges $c_{i,0} \mapright{\perp_1} c_{i,1}$ for all $i =
    0,\ldots,k$.

-   There exist edges $c_{i,j} \mapright{a_1} c_{i,j+1}$ for all $i =
    0,\ldots,k$ and $j = 1,\ldots,m'_k$.

-   There exist edges $d_{i,1} \mapright{\perp_2} d_{i,0}$ for all $i =
    0,\ldots,k$.

-   There exist edges $d_{i,j+1} \mapright{a_2} d_{i,j}$ for all $i =
    0,\ldots,k$ and $j = 1,\ldots,n'_k$.

-   There exist edges $c_{i,m_i+1} \vlongmapright{q_1^{(i)},q_2^{(i)}}
    d_{i,n_i+1}$ for all $i = 0,\ldots,k$.

![The automaton $\mathcal{B}_{m,n}^{(k)}$[]{data-label="fig3"}](automaton-associatedID.eps)

\[config\] Let $\mathcal{M}$ be a normalized $CM(2)$ and let $m,n,k \in \mathbb{N}$. Then $\mathcal{B}_{m,n}^{(k)}$ is a finite approximation of $\mathcal{A}(X,\mathcal{T};w_{m,n})$.

We use induction on $k$. Clearly, $\mathcal{B}_{m,n}^{(0)}$ is the Munn tree of $w_{m,n}$ with the edge $c_{0,m+1} \mapright{\iota_2}
d_{0,n+1}$ adjoined. Since $\iota_1 = \iota_2$ is a relation of $\mathcal{T}$, the lemma holds for $k = 0$.

Assume now that $k > 0$ and $\mathcal{B}_{m,n}^{(k-1)}$ is a finite approximation of the [[Schützenberger ]{}]{}automaton $\mathcal{A}(X,\mathcal{T};w_{m,n})$. Assume that $$(\iota,m,n) \vdash_{\mathcal{M}}^{k-1} (q^{(k-1)},m_{k-1},n_{k-1})
\vdash_{\mathcal{M}} (q^{(k)},m_k,n_k).$$ Then $(q^{(k-1)},i,x,q^{(k)}) \in \delta$ for some $i \in \{ 1,2\}$ (assume $i = 1$ for simplicity, the case $i = 2$ being analogous) and $$x = \left\{
\begin{array}{ll}
a&\mbox{ if }m_{k} = m_{k-1} > 0\\
\perp&\mbox{ if }m_{k} = m_{k-1} = 0\\
+&\mbox{ if }m_{k} = m_{k-1} +1\\
-&\mbox{ if }m_{k} = m_{k-1} -1
\end{array}
\right.$$ The instruction $(q^{(k-1)},1,x,q^{(k)})$ produces a relation $syq_1^{(k-1)} = st_1zq_1^{(k)}t_1{^{-1}}$ in $\mathcal{T}_1^t \cup \mathcal{T}_1^w \cup \mathcal{T}_1^e$ with $y =
a_1$ if $x = -$ and $y = 1$ otherwise, and $z =
a_1$ if $x = +$ and $z = 1$ otherwise. Using $s = \perp_1$ or $a_1$ according to the values of $m_{k-1}$ and $y$, we can now use this relation to perform an expansion of the path $$c_{k-1, m_{k-1}-|y|}\vlongmapright{syq_1^{(k-1)}} d_{k-1, n_{k-1}+1}$$ to get after subsequent folding the edges $$c_{k,m_k+1}\mapright{q_1^{(k)}}d_{k,n_k+1}, c_{k-1,m_k+\varepsilon}\mapright{t_1}c_{k,m_k+\varepsilon}$$ for $\varepsilon = 0$ or $1$, $d_{k-1,n_k+1} \mapright{t_1} d_{k,n_k+1}$ and possibly also an edge of the form $c_{k,m_k} \mapright{a_1}
c_{k,m_k+1}$. It is straightforward to check that, applying now the relations from $\mathcal{T}_1^c \cup
\mathcal{T}_2^c$, followed by $t_1 = t_2$ and $q_1^{(k)} = q_2^{(k)}$, we get precisely $\mathcal{B}_{m,n}^{(k)}$. Note that if $m_k
=m'_{k-1} +1$, we get an edge $c_{k,m'_{k-1}+1} \mapright{a_1}
c_{k,m'_k+1}$ through the expansion, and the application of the relations from $\mathcal{T}_1^c$ yields indeed the required extra column of $\mathcal{B}_{m,n}^{(k)}$ with respect to $\mathcal{B}_{m,n}^{(k-1)}$. Therefore $\mathcal{B}_{m,n}^{(k)}$ is a finite approximation of $\mathcal{A}(X,\mathcal{T};w_{m,n})$ and the lemma is proved.

It follows from the definition that $\mathcal{B}_{m,n}^{(k-1)}$ embeds in $\mathcal{B}_{m,n}^{(k)}$ for every $k \geq 1$. Therefore we can define $\mathcal{B}_{m,n}$ as the colimit of the sequence $(\mathcal{B}_{m,n}^{(k)})_k$, where all the $\mathcal{B}_{m,n}^{(k)}$ embed. This colimit may be finite or infinite, depending on whether or not the computation in $\mathcal{M}$ halts when we start with the configuration $(\iota,m,n)$.

Let $\mathcal{C}$ denote the finite complete inverse $X$-automaton with a single vertex.

\[computsch\] Let $\mathcal{M}$ be a normalized $CM(2)$ and let $m,n \in \mathbb{N}$. Then $$\mathcal{A}(X,\mathcal{T};w_{m,n}) = \left\{
\begin{array}{ll}
\mathcal{C} & \mbox{ if $(m,n)$ is accepted by }\mathcal{M}\\
\mathcal{B}_{m,n} & \mbox{otherwise}
\end{array}
\right.$$

First of all, we claim that $\mathcal{B}_{m,n}$ is closed under all relations of $\mathcal{T} \setminus (\mathcal{T}_1^f \cup
\mathcal{T}_2^f)$. This is immediate for all the relations in $\mathcal{T}_1^c \cup \mathcal{T}_2^c \cup \mathcal{T}_3$. Since $\mathcal{M}$ is deterministic, reversible and alternating, it is also true for relations in $\mathcal{T}_i^t \cup \mathcal{T}_i^w \cup
\mathcal{T}_i^e$: no $Q$-edge can be involved in more than one expansion. For instance, reversibility prevents the appearance in line $i-1$ of some new $Q$-edge obtained through an expansion of a $Q$-edge in line $i$.

Now, if $(m,n)$ is accepted by $\mathcal{M}$, then $f$ labels some edge in $\mathcal{B}^{(k)}_{m,n}$ for some $k$ and so the relations of $\mathcal{T}_1^f \cup \mathcal{T}_2^f$ eventually collapse $\mathcal{B}^{(k)}_{m,n}$ into $\mathcal{C}$. Since $\mathcal{B}^{(k)}_{m,n}$ is a finite approximation of $\mathcal{A}(X,\mathcal{T};w_{m,n})$, it follows that $\mathcal{A}(X,\mathcal{T};w_{m,n}) = \mathcal{C}$.

Finally, assume that $(m,n)$ is not accepted by $\mathcal{M}$. It is straightforward to check that in this case $\mathcal{B}_{m,n}$ must be also closed under $\mathcal{T}_1^f \cup
\mathcal{T}_2^f$, hence $\mathcal{B}_{m,n}$ is $\mathcal{T}$-closed. Since $\mathcal{B}^{(k)}_{m,n}$ is a finite approximation of $\mathcal{A}(X,\mathcal{T};w_{m,n})$, we have $L(\mathcal{B}^{(k)}_{m,n})
\subseteq L(\mathcal{A}(X,\mathcal{T};w_{m,n}))$ for every $k$. Hence $$L(\mathcal{B}_{m,n}) = \bigcup_{k \geq 0} L(\mathcal{B}^{(k)}_{m,n})
\subseteq L(\mathcal{A}(X,\mathcal{T};w_{m,n})).$$ Since $\mathcal{A}(X,\mathcal{T};w_{m,n})$ is the smallest $\mathcal{T}$-closed inverse $X$-automaton recognizing $w_{m,n}$, it follows that $\mathcal{A}(X,\mathcal{T};w_{m,n}) = \mathcal{B}_{m,n}$ as claimed.

Since $\mathcal{C}$ is the [[Schützenberger ]{}]{}automaton of the zero of $S$, we immediately get:

\[theequiv\] Let $\mathcal{M}$ be a normalized $CM(2)$ and let $m,n \in \mathbb{N}$. Then $w_{m,n} = 0$ in the associated amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ if and only if $(m,n)$ is accepted by $\mathcal{M}$.

We can now prove our main result:

The word problem for an amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ of inverse semigroups may be undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{R}$-classes and $\omega_1,\omega_2$ to be computable functions.

If the word problem would be decidable in these circumstances, then, in view of Proposition \[finiter\] and Theorem \[theequiv\], we could decide whether or not a normalized $CM(2)$ accepts a given $(m,n) \in
\mathbb{N}^2$. And the latter is undecidable, even when we consider the single $CM(2)$ $\mathcal{M}^*$ of Corollary \[cor:universal\].

As a consequence of Theorem \[theequiv\] we have also the following:

Checking finiteness for a $\mathcal{D}$-class of an amalgam $[S_1,S_2;U,\omega_1,\omega_2]$ of inverse semigroups may be undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{D}$-classes.

Clearly, checking the finiteness of a $\mathcal{D}$-class of a word $w$ in $S_1*_U S_2$ is equivalent to check whether or not the corresponding [[Schützenberger ]{}]{}automaton is finite. Consider again the $CM(2)$ $\mathcal{M}^*$ of Corollary \[cor:universal\] and the associated amalgam. By Proposition \[computsch\], if $\mathcal{A}(X,\mathcal{T};w_{m,n})$ would be infinite, then $(m,n)$ is not accepted by $\mathcal{M}^*$. On the other hand, if $\mathcal{A}(X,\mathcal{T};w_{m,n})$ would be finite, we could use the Stephen’s sequence to actually compute it [@Steph] and decide whether or not $\mathcal{M}^*$ accepts $(m,n)$. Therefore we cannot decide whether or not $\mathcal{A}(X,\mathcal{T};w_{m,n})$ is finite.

Acknowledgments {#acknowledgments .unnumbered}
===============

Both authors acknowledge support from C.M.U.P., financed by F.C.T. (Portugal) through the programmes POCTI and POSI, with national and E.U. structural funds. The first-named author acknowledges also the support of the FCT project SFRH/BPD/65428/2009.


Q:

how do i create this type of element in javascript

I have the following HTML:
<fb:like show_faces="false" action='like'/>

How do I convert this to JavaScript (no jQuery) Specifically, create an element like so..
I hope this question does not get marked as closed I dont really know what to do so I dont have any more code samples.
Thanks.

A:

var test = document.createElement("fb:like");
test.setAttribute("show_faces", "false");
test.setAttribute("action", "like");


A randomized trial on sodium reduction in two developing countries.
Hypertension remains the most common cardiovascular risk factor in developing countries, yet the majority of patients have no access to pharmacological therapy. Population-wide preventive strategies, such as salt restriction, are an attractive alternative, but experience in resource-poor settings is limited. To address this question, we conducted a randomized crossover study of salt restriction in adults living in Nigeria and Jamaica in order to estimate the mean blood pressure (BP) response. After a 4-week run-in period to determine willingness to adhere to a low-salt diet, 56 Jamaicans and 58 Nigerians completed an 8-week crossover study of low-salt and high-salt intake. Baseline BPs were in the normotensive range (systolic=125 mmHg in Jamaica, 114 mmHg in Nigeria). Baseline urinary sodium excretion was 86.8 and 125.6 mEq/day in Nigeria and Jamaica, respectively. The mean difference between urinary sodium excretion at baseline and at the end of the 3-week low-sodium phase was 33.6 mEq/day in Nigeria and 57.5 mEq/day in Jamaica. During the high-sodium phase, mean change in urinary sodium excretion from baseline to week 3 was 35.0 and 5.5 mEq/day in Nigeria and Jamaica, respectively. The mean change in systolic BP ('high' vs 'low' sodium phase) was approximately 5 mmHg in both groups. This study suggests that the efficacy of sodium reduction in developing countries equals those noted in more affluent cultures. If promoted on a wide scale, sodium reduction could be used to treat persons with established hypertension, and more importantly, to prevent age-related increases in BP in poor communities.


Please use this application form for the pre-university, undergraduate and postgraduate scholarships,including the MBA Scholarship Awards. For all other applications or questions, please emailinfo@ydd.org.my.APPLICATION REQUIREMENTS

1.Please complete all sections of the application form, including attaching your photo and signing theacknowledgement page.2.Email the completed application form, along with scanned copies of the signed acknowledgementpage, original academic transcripts, official certificates, college/university offer letter and other relevantattachments in PDF file to: info@ydd.org.my3.Only shortlisted Applicants will be notified.


The transport of organelles and macromolecular complexes through the cytoplasm is essential for the function of every eukaryotic cell. This process is performed by motor proteins that move their cargo along microtubules and actin filaments. The spatial and temporal control of motor-dependent transport is critical for cell division, organelle transport and positioning, and the movement of RNA and protein complexes within the cell. The goal of this proposal is to understand the molecular mechanisms, which regulate organelle transport and coordinate the work of molecular motors. Our previous work established a permanent cell line of pigment cells (melanophores) from the frog Xenopus laevis as a model system to study the regulation of organelle movement. Movement of pigment organelles in these cells is initiated by changes in the concentration of cAMP and is performed by two microtubule motors of opposite polarity, cytoplasmic dynein and kinesin-II, and an actin motor, myosin-V. Organelle transport by these three motors is regulated by intracellular cAMP concentration. Furthermore, the activity of two microtubule motors is coordinated. This proposal has three specific aims: (i) find what regulates organelle transport along microtubules in the melanophore system: we will identify differentially regulated protein kinase(s) bound to organelles and determine how they regulate organelle transport; (ii) find the mechanism of coordination between plus and minus-end movement of pigment organelles along microtubules: we will determine if coordination is governed by cooperative differential binding of plus and minus-end directed motors to receptor proteins on the surface of organelles or it is determined by a stochastic mechanism; (iii) find how myosin-V is regulated in melanophores and other cell types: we will explore mechanisms of regulation of myosin-V in interphase cells using Xenopus melanophores and mouse macrophages and determine the role of p21-activated kinase (PAK1) in its regulation.


/*
 * Copyright 2002-2018 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.springframework.jdbc.core.namedparam;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.springframework.dao.InvalidDataAccessApiUsageException;
import org.springframework.jdbc.core.SqlParameter;
import org.springframework.jdbc.core.SqlParameterValue;
import org.springframework.lang.Nullable;
import org.springframework.util.Assert;

/**
 * Helper methods for named parameter parsing.
 *
 *
Only intended for internal use within Spring's JDBC framework.
 *
 * @author Thomas Risberg
 * @author Juergen Hoeller
 * @since 2.0
 */
public abstract class NamedParameterUtils {

	/**
	 * Set of characters that qualify as comment or quotes starting characters.
	 */
	private static final String[] START_SKIP = new String[] {"'", "\"", "--", "/*"};

	/**
	 * Set of characters that at are the corresponding comment or quotes ending characters.
	 */
	private static final String[] STOP_SKIP = new String[] {"'", "\"", "\n", "*/"};

	/**
	 * Set of characters that qualify as parameter separators,
	 * indicating that a parameter name in a SQL String has ended.
	 */
	private static final String PARAMETER_SEPARATORS = "\"':&,;()|=+-*%/\\<>^";

	/**
	 * An index with separator flags per character code.
	 * Technically only needed between 34 and 124 at this point.
	 */
	private static final boolean[] separatorIndex = new boolean[128];

	static {
		for (char c : PARAMETER_SEPARATORS.toCharArray()) {
			separatorIndex[c] = true;
		}
	}

	//-------------------------------------------------------------------------
	// Core methods used by NamedParameterJdbcTemplate and SqlQuery/SqlUpdate
	//-------------------------------------------------------------------------

	/**
	 * Parse the SQL statement and locate any placeholders or named parameters.
	 * Named parameters are substituted for a JDBC placeholder.
	 * @param sql the SQL statement
	 * @return the parsed statement, represented as ParsedSql instance
	 */
	public static ParsedSql parseSqlStatement(final String sql) {
		Assert.notNull(sql, "SQL must not be null");

		Set<String> namedParameters = new HashSet<>();
		String sqlToUse = sql;
		List<ParameterHolder> parameterList = new ArrayList<>();

		char[] statement = sql.toCharArray();
		int namedParameterCount = 0;
		int unnamedParameterCount = 0;
		int totalParameterCount = 0;

		int escapes = 0;
		int i = 0;
		while (i < statement.length) {
			int skipToPosition = i;
			while (i < statement.length) {
				skipToPosition = skipCommentsAndQuotes(statement, i);
				if (i == skipToPosition) {
					break;
				}
				else {
					i = skipToPosition;
				}
			}
			if (i >= statement.length) {
				break;
			}
			char c = statement[i];
			if (c == ':' || c == '&') {
				int j = i + 1;
				if (c == ':' && j < statement.length && statement[j] == ':') {
					// Postgres-style "::" casting operator should be skipped
					i = i + 2;
					continue;
				}
				String parameter = null;
				if (c == ':' && j < statement.length && statement[j] == '{') {
					// :{x} style parameter
					while (statement[j] != '}') {
						j++;
						if (j >= statement.length) {
							throw new InvalidDataAccessApiUsageException("Non-terminated named parameter declaration " +
									"at position " + i + " in statement: " + sql);
						}
						if (statement[j] == ':' || statement[j] == '{') {
							throw new InvalidDataAccessApiUsageException("Parameter name contains invalid character '" +
									statement[j] + "' at position " + i + " in statement: " + sql);
						}
					}
					if (j - i > 2) {
						parameter = sql.substring(i + 2, j);
						namedParameterCount = addNewNamedParameter(namedParameters, namedParameterCount, parameter);
						totalParameterCount = addNamedParameter(
								parameterList, totalParameterCount, escapes, i, j + 1, parameter);
					}
					j++;
				}
				else {
					while (j < statement.length && !isParameterSeparator(statement[j])) {
						j++;
					}
					if (j - i > 1) {
						parameter = sql.substring(i + 1, j);
						namedParameterCount = addNewNamedParameter(namedParameters, namedParameterCount, parameter);
						totalParameterCount = addNamedParameter(
								parameterList, totalParameterCount, escapes, i, j, parameter);
					}
				}
				i = j - 1;
			}
			else {
				if (c == '\\') {
					int j = i + 1;
					if (j < statement.length && statement[j] == ':') {
						// escaped ":" should be skipped
						sqlToUse = sqlToUse.substring(0, i - escapes) + sqlToUse.substring(i - escapes + 1);
						escapes++;
						i = i + 2;
						continue;
					}
				}
				if (c == '?') {
					int j = i + 1;
					if (j < statement.length && (statement[j] == '?' || statement[j] == '|' || statement[j] == '&')) {
						// Postgres-style "??", "?|", "?&" operator should be skipped
						i = i + 2;
						continue;
					}
					unnamedParameterCount++;
					totalParameterCount++;
				}
			}
			i++;
		}
		ParsedSql parsedSql = new ParsedSql(sqlToUse);
		for (ParameterHolder ph : parameterList) {
			parsedSql.addNamedParameter(ph.getParameterName(), ph.getStartIndex(), ph.getEndIndex());
		}
		parsedSql.setNamedParameterCount(namedParameterCount);
		parsedSql.setUnnamedParameterCount(unnamedParameterCount);
		parsedSql.setTotalParameterCount(totalParameterCount);
		return parsedSql;
	}

	private static int addNamedParameter(
			List<ParameterHolder> parameterList, int totalParameterCount, int escapes, int i, int j, String parameter) {

		parameterList.add(new ParameterHolder(parameter, i - escapes, j - escapes));
		totalParameterCount++;
		return totalParameterCount;
	}

	private static int addNewNamedParameter(Set<String> namedParameters, int namedParameterCount, String parameter) {
		if (!namedParameters.contains(parameter)) {
			namedParameters.add(parameter);
			namedParameterCount++;
		}
		return namedParameterCount;
	}

	/**
	 * Skip over comments and quoted names present in an SQL statement.
	 * @param statement character array containing SQL statement
	 * @param position current position of statement
	 * @return next position to process after any comments or quotes are skipped
	 */
	private static int skipCommentsAndQuotes(char[] statement, int position) {
		for (int i = 0; i < START_SKIP.length; i++) {
			if (statement[position] == START_SKIP[i].charAt(0)) {
				boolean match = true;
				for (int j = 1; j < START_SKIP[i].length(); j++) {
					if (statement[position + j] != START_SKIP[i].charAt(j)) {
						match = false;
						break;
					}
				}
				if (match) {
					int offset = START_SKIP[i].length();
					for (int m = position + offset; m < statement.length; m++) {
						if (statement[m] == STOP_SKIP[i].charAt(0)) {
							boolean endMatch = true;
							int endPos = m;
							for (int n = 1; n < STOP_SKIP[i].length(); n++) {
								if (m + n >= statement.length) {
									// last comment not closed properly
									return statement.length;
								}
								if (statement[m + n] != STOP_SKIP[i].charAt(n)) {
									endMatch = false;
									break;
								}
								endPos = m + n;
							}
							if (endMatch) {
								// found character sequence ending comment or quote
								return endPos + 1;
							}
						}
					}
					// character sequence ending comment or quote not found
					return statement.length;
				}
			}
		}
		return position;
	}

	/**
	 * Parse the SQL statement and locate any placeholders or named parameters. Named
	 * parameters are substituted for a JDBC placeholder, and any select list is expanded
	 * to the required number of placeholders. Select lists may contain an array of
	 * objects, and in that case the placeholders will be grouped and enclosed with
	 * parentheses. This allows for the use of "expression lists" in the SQL statement
	 * like:

	 * {@code select id, name, state from table where (name, age) in (('John', 35), ('Ann', 50))}
	 *
The parameter values passed in are used to determine the number of placeholders to
	 * be used for a select list. Select lists should be limited to 100 or fewer elements.
	 * A larger number of elements is not guaranteed to be supported by the database and
	 * is strictly vendor-dependent.
	 * @param parsedSql the parsed representation of the SQL statement
	 * @param paramSource the source for named parameters
	 * @return the SQL statement with substituted parameters
	 * @see #parseSqlStatement
	 */
	public static String substituteNamedParameters(ParsedSql parsedSql, @Nullable SqlParameterSource paramSource) {
		String originalSql = parsedSql.getOriginalSql();
		List<String> paramNames = parsedSql.getParameterNames();
		if (paramNames.isEmpty()) {
			return originalSql;
		}
		StringBuilder actualSql = new StringBuilder(originalSql.length());
		int lastIndex = 0;
		for (int i = 0; i < paramNames.size(); i++) {
			String paramName = paramNames.get(i);
			int[] indexes = parsedSql.getParameterIndexes(i);
			int startIndex = indexes[0];
			int endIndex = indexes[1];
			actualSql.append(originalSql, lastIndex, startIndex);
			if (paramSource != null && paramSource.hasValue(paramName)) {
				Object value = paramSource.getValue(paramName);
				if (value instanceof SqlParameterValue) {
					value = ((SqlParameterValue) value).getValue();
				}
				if (value instanceof Collection) {
					Iterator<?> entryIter = ((Collection<?>) value).iterator();
					int k = 0;
					while (entryIter.hasNext()) {
						if (k > 0) {
							actualSql.append(", ");
						}
						k++;
						Object entryItem = entryIter.next();
						if (entryItem instanceof Object[]) {
							Object[] expressionList = (Object[]) entryItem;
							actualSql.append('(');
							for (int m = 0; m < expressionList.length; m++) {
								if (m > 0) {
									actualSql.append(", ");
								}
								actualSql.append('?');
							}
							actualSql.append(')');
						}
						else {
							actualSql.append('?');
						}
					}
				}
				else {
					actualSql.append('?');
				}
			}
			else {
				actualSql.append('?');
			}
			lastIndex = endIndex;
		}
		actualSql.append(originalSql, lastIndex, originalSql.length());
		return actualSql.toString();
	}

	/**
	 * Convert a Map of named parameter values to a corresponding array.
	 * @param parsedSql the parsed SQL statement
	 * @param paramSource the source for named parameters
	 * @param declaredParams the List of declared SqlParameter objects
	 * (may be {@code null}). If specified, the parameter metadata will
	 * be built into the value array in the form of SqlParameterValue objects.
	 * @return the array of values
	 */
	public static Object[] buildValueArray(
			ParsedSql parsedSql, SqlParameterSource paramSource, @Nullable List<SqlParameter> declaredParams) {

		Object[] paramArray = new Object[parsedSql.getTotalParameterCount()];
		if (parsedSql.getNamedParameterCount() > 0 && parsedSql.getUnnamedParameterCount() > 0) {
			throw new InvalidDataAccessApiUsageException(
					"Not allowed to mix named and traditional ? placeholders. You have " +
					parsedSql.getNamedParameterCount() + " named parameter(s) and " +
					parsedSql.getUnnamedParameterCount() + " traditional placeholder(s) in statement: " +
					parsedSql.getOriginalSql());
		}
		List<String> paramNames = parsedSql.getParameterNames();
		for (int i = 0; i < paramNames.size(); i++) {
			String paramName = paramNames.get(i);
			try {
				Object value = paramSource.getValue(paramName);
				SqlParameter param = findParameter(declaredParams, paramName, i);
				paramArray[i] = (param != null ? new SqlParameterValue(param, value) : value);
			}
			catch (IllegalArgumentException ex) {
				throw new InvalidDataAccessApiUsageException(
						"No value supplied for the SQL parameter '" + paramName + "': " + ex.getMessage());
			}
		}
		return paramArray;
	}

	/**
	 * Find a matching parameter in the given list of declared parameters.
	 * @param declaredParams the declared SqlParameter objects
	 * @param paramName the name of the desired parameter
	 * @param paramIndex the index of the desired parameter
	 * @return the declared SqlParameter, or {@code null} if none found
	 */
	@Nullable
	private static SqlParameter findParameter(
			@Nullable List<SqlParameter> declaredParams, String paramName, int paramIndex) {

		if (declaredParams != null) {
			// First pass: Look for named parameter match.
			for (SqlParameter declaredParam : declaredParams) {
				if (paramName.equals(declaredParam.getName())) {
					return declaredParam;
				}
			}
			// Second pass: Look for parameter index match.
			if (paramIndex < declaredParams.size()) {
				SqlParameter declaredParam = declaredParams.get(paramIndex);
				// Only accept unnamed parameters for index matches.
				if (declaredParam.getName() == null) {
					return declaredParam;
				}
			}
		}
		return null;
	}

	/**
	 * Determine whether a parameter name ends at the current position,
	 * that is, whether the given character qualifies as a separator.
	 */
	private static boolean isParameterSeparator(char c) {
		return (c < 128 && separatorIndex[c]) || Character.isWhitespace(c);
	}

	/**
	 * Convert parameter types from an SqlParameterSource into a corresponding int array.
	 * This is necessary in order to reuse existing methods on JdbcTemplate.
	 * Any named parameter types are placed in the correct position in the
	 * Object array based on the parsed SQL statement info.
	 * @param parsedSql the parsed SQL statement
	 * @param paramSource the source for named parameters
	 */
	public static int[] buildSqlTypeArray(ParsedSql parsedSql, SqlParameterSource paramSource) {
		int[] sqlTypes = new int[parsedSql.getTotalParameterCount()];
		List<String> paramNames = parsedSql.getParameterNames();
		for (int i = 0; i < paramNames.size(); i++) {
			String paramName = paramNames.get(i);
			sqlTypes[i] = paramSource.getSqlType(paramName);
		}
		return sqlTypes;
	}

	/**
	 * Convert parameter declarations from an SqlParameterSource to a corresponding List of SqlParameters.
	 * This is necessary in order to reuse existing methods on JdbcTemplate.
	 * The SqlParameter for a named parameter is placed in the correct position in the
	 * resulting list based on the parsed SQL statement info.
	 * @param parsedSql the parsed SQL statement
	 * @param paramSource the source for named parameters
	 */
	public static List<SqlParameter> buildSqlParameterList(ParsedSql parsedSql, SqlParameterSource paramSource) {
		List<String> paramNames = parsedSql.getParameterNames();
		List<SqlParameter> params = new ArrayList<>(paramNames.size());
		for (String paramName : paramNames) {
			params.add(new SqlParameter(
					paramName, paramSource.getSqlType(paramName), paramSource.getTypeName(paramName)));
		}
		return params;
	}

	//-------------------------------------------------------------------------
	// Convenience methods operating on a plain SQL String
	//-------------------------------------------------------------------------

	/**
	 * Parse the SQL statement and locate any placeholders or named parameters.
	 * Named parameters are substituted for a JDBC placeholder.
	 *
This is a shortcut version of
	 * {@link #parseSqlStatement(String)} in combination with
	 * {@link #substituteNamedParameters(ParsedSql, SqlParameterSource)}.
	 * @param sql the SQL statement
	 * @return the actual (parsed) SQL statement
	 */
	public static String parseSqlStatementIntoString(String sql) {
		ParsedSql parsedSql = parseSqlStatement(sql);
		return substituteNamedParameters(parsedSql, null);
	}

	/**
	 * Parse the SQL statement and locate any placeholders or named parameters.
	 * Named parameters are substituted for a JDBC placeholder and any select list
	 * is expanded to the required number of placeholders.
	 *
This is a shortcut version of
	 * {@link #substituteNamedParameters(ParsedSql, SqlParameterSource)}.
	 * @param sql the SQL statement
	 * @param paramSource the source for named parameters
	 * @return the SQL statement with substituted parameters
	 */
	public static String substituteNamedParameters(String sql, SqlParameterSource paramSource) {
		ParsedSql parsedSql = parseSqlStatement(sql);
		return substituteNamedParameters(parsedSql, paramSource);
	}

	/**
	 * Convert a Map of named parameter values to a corresponding array.
	 *
This is a shortcut version of
	 * {@link #buildValueArray(ParsedSql, SqlParameterSource, java.util.List)}.
	 * @param sql the SQL statement
	 * @param paramMap the Map of parameters
	 * @return the array of values
	 */
	public static Object[] buildValueArray(String sql, Map<String, ?> paramMap) {
		ParsedSql parsedSql = parseSqlStatement(sql);
		return buildValueArray(parsedSql, new MapSqlParameterSource(paramMap), null);
	}

	private static class ParameterHolder {

		private final String parameterName;

		private final int startIndex;

		private final int endIndex;

		public ParameterHolder(String parameterName, int startIndex, int endIndex) {
			this.parameterName = parameterName;
			this.startIndex = startIndex;
			this.endIndex = endIndex;
		}

		public String getParameterName() {
			return this.parameterName;
		}

		public int getStartIndex() {
			return this.startIndex;
		}

		public int getEndIndex() {
			return this.endIndex;
		}
	}

}


Royal Bank of Scotland – a nice little earner

There has been understandable and predictableoutrage at the size of Stephen Hester’s pay packet at the Royal Bank of Scotland. But, while I share the anger, it is not entirely a straightforward issue. The government can at least claim that he will only get top whack if he helps the tax-payer make a profit of the sums used to rescue RBS – a useful reminder that the bank bail-outs were not simple hand-outs of public cash.

There are at least four issues raised by the size of his pay-packet.

The high rewards that all top bankers expect

Why some people need incentives to do their job

What exactly has he been incentivised to do

Whether RBS top-dogs should be treated differently because it is now largely state-owned

Public outrage is undoubtedly a reflection of wider anger at boardroom excess, mixed up with the sense that this is public money because RBS is quasi-nationalised. Richard Murphy points out the make-up of UKFI’s board who approved this.

I hope that there is also some discussion of the other two. There’s a tantalising snippet on PA about some new research that shows incentives can be counter-productive. While some systems are better than others – eg incentives that rewards teams, rather than pitting individuals against each other – I’ve never been convinced that performance related pay achieves very much. Inevitably winners take it granted, and the losers take it personally.

But the big issue that does not seem to have received much comment is exactly what Mr Hester has been told to do to get his dosh. Frankly public ownership is such anathema to any red-blooded banker that they hardly need incentivising for getting back into the private sector.

Yet from the government’s perspective getting the finance system working should take priority over early pay back. Because many foreign banks have stopped lending in the UK, British based banks need to lend more than they did before the recession to get credit functioning properly again. However this is not necessarily the way to boost RBS’s share price. And if that produces more growth, then there will be more benefit to the tax payer than a simple return on privatising RBS sooner rather than later.

If we have to have incentives in public stake banks, then at least they should serve public policy objectives.

Written by Nigel Stanley

I was the TUC’s Head of Campaigns and Communications until semi-retiring in May 2015, I started at the TUC in 1994.

My interests cover a wide range of communications and politics related issues, but if I have a specialist subject, itR…


The art of stealth centers on the ability to hide in plain sight - something particularly difficult when bickering loudly.

"You can't seriously be backing out now! I can't carry a week's worth of food by myself!"

"That's sounds an awful lot like your problem and not mine. This is your idea, after all."

"Well, you're already out of uniform and wearing the backpack, so you're staying in this or so help me, I will break you."

"Relax, Em, I was just kidding," Mercury said dismissively. Emerald's cutting glare wasn't buying it, though. "I'm doing this so I don't have to get up in the mornings all the time, so you can at least trust me there."

"Yeah, because you're a lazy ass."

"I prefer to think of it as expending the least amount of energy while getting the most amount of reward. You should try it sometime."

"Ugh, bite me."

While there was no express curfew at Beacon, not many students were up at the late, late hour of 11:25 in the evening. Hunter training was no joke – most people would be exhausted by the end of the day, as they can be seen moving sluggishly about during dinner time. At the moment, almost everyone had retired to their rooms, leaving the moon-lit halls almost totally empty. Amateurs. The pair of delinquents, on the other hand, already had the unofficial training of upper-level students and, on top of that, were well-accustomed to operating at night. There would be no interference with their plan.

Although they had only just arrived at the school earlier that day, Mercury and Emerald already had a general grasp of how to navigate Beacon. Most of the important rooms, such as classrooms, the dining hall, and the auditorium, were centrally located with the dorms expanding outward from them. There, in the center, was their target: the kitchen.

The pair reached the central lobby. "How much further do we have to go?" Emerald turned her head to ask.

"Well, the mess hall is right over… there," Mercury answered, pointing toward the southern double doors of the hall. "The kitchen has to be attached to it somewhere."

"Alright, so through the mess hall it is." Emerald strode over to the huge wooden doors that lead to the dining hall and gave the handle a good shake. "Of course it's locked."

"I could kick it down," Mercury offered helpfully.

"And leave a broken lock to raise suspicion? Really?"

Mercury merely shrugged in his usual manner. "It's always an option."

Emerald rolled her eyes. "Sure. Anyway, we've got to find a different way to get to the kitchen. There has to be another way in…"

"I remember the elevators have a maintenance floor below this ground floor, but you had to have a key to access it."

"Lovely suggestion."

"There could be stairs leading down there as well. Perhaps we can get to the kitchen from below? There ought to be a loading dock for food to come in."

"Well, there was a key preventing us to go down on the elevator, I doubt the stairs will be any better. No, there has to be a way to get there on this fl—"

Mercury suddenly interrupted her as he pushed her toward the wall with a figure above his lips. Before Emerald could let out a protest, she heard it, too – two pairs of footsteps and two voices.

"…now's not really the time. Can't you wait until the weekend?" a calm, male voice asked.

"I can't wait anymore! Come on, no one will find out in the kitchen!" an excited, almost bubbly, female voice replied.

"Alright, alright, just don't be so wild. People might hear us this time."

The female voice giggled. "Aw, don't worry, I'll be gentle!"

After the footsteps started heading away, Mercury spoke up. "Are they… doing what I think they're about to do?"

"I don't care what they're going, only where they're doing it. Come on, let's follow them."

Mercury was doing his best to ignore the conversation the two shadows were having out in front of him, but his mind was already going weird places.

"You forgot to bring that special something, didn't you," the male voice deadpanned.

"Maybe just a little bit… we can still do it without it though! Right?"

"You and I both know that's not a smart idea. It's not going to come out right without it, and I know how much you like its taste."

"Fiiiine," the female voice conceded with a whine. "Let's go back to get it – then we can have our fun time!" Uh oh.

"Of course." Mercury grabbed Emerald and pulled the two of them into a gap in the hall and waited for the pair of silhouettes to hurry past them. Once they were out of earshot, he let go and stepped back out in the dim hallway.

"Okay, I'm not just imagining things here, am I? Those two were definitely planning on boning in the kitchen."

"…I'm just going to pretend that never happened." Mercury could practically hear his partner roll her eyes in disgust. "Come on, they said they were going to be back soon, so we should hurry up and gather what we can before they notice us."

"You got it, boss," he replied sardonically, but he nevertheless followed Emerald's lead to the metal doors where the shadows had stood earlier. Yup, definitely the kitchen, alright, Mercury thought as he sniffed the air – there were still faint traces of the dinner from earlier wafting in through the doors. I have to wonder, though…

"Hey, Em?"

"Yeah?" She was already inside, seeking out where the pantry might be.

"You reckon that smell is a kink?"

The thief froze in the middle of loading her first handful of energy bars into her bag. Slowly, she turned around and eyed Mercury with an incredulous expression. "How… how would that even work? And why the hell are you still thinking about that?"

"Well, I heard once that our sense of smell is one of the most powerful mental triggers," Mercury responded wistfully, setting down his own bag to shovel in the nearest food at hand. "So, if you think about it, doing the do in place that's filled with all these smells has got to be someone's way of getting off."

"Mercury, that's disg—" Emerald flared up but quickly paused to think. "Well, I suppose you're not wrong. Still, doing it in the kitchen sounds gross. I don't want someone's junk all up in the place that makes the food I'm going to be eating."

Mercury shuddered at the thought. "Good point." The pair continued their work in silence, moving around the pantry and selecting all the non-perishable items they could find and fit in their surprisingly roomy bags. They took a little from each pile of goods so as not to alert the cooks in the morning about their presence. It was an easy enough job, but easy means boring, and boredom makes Mercury ask odd questions.

"Em, what's your favorite scent?"

The sound of cans clanging against on another from her part of the room ceased. "Why would you care?"

"Just curious and bored. I'm sure I'll find some way to hold it against you, but that'll be later."

"How thoughtful of you," Emerald icily retorted. Still no movement from her end, though. "I'd have to say… smoke. I like the smell of smoke and things burning."

"Well, doesn't that sound twisted."

"Oh, up yours. What about you, then?"

Mercury didn't have time to respond, but a newcomer sure did. "Ooo, I can't wait anymore! Let's start already!" It was the female voice from earlier, cheering out as the metal doors to the kitchen swung open with a loud "bang!"

"Alright, alright, let's clear a space on the counter first," the male voice softly replied.

The food burglars were still hidden in the pantry, but with the two other people in the kitchen, there was no way for them to get out undetected. Mercury looked over to Emerald, who was brimming with frustration. "Damn it!" she whispered harshly. "Are we seriously going to have to wait through their lovemaking?"

"Who knows? He might be a quick one," Mercury helpfully suggested. Truthfully, he was a little annoyed himself that they had to wait there on the hard linoleum floor for an indefinite amount of time, but there was no use being angry. Besides, when life gives you lemons...

Mercury scooted up to the door of the pantry and pressed his ear against it, ignoring the dirty glare from Emerald. What he heard was a surprise indeed.

"No, silly, you gotta make it all creamy-like with this!" Pots and pans banged up against each other.

"I don't think that's really make it come out right," the male voice said with worry.

"Aww, c'mon, where's your sense of experimentation?" Experimentation? This is going to be good.

"That's not the problem; the problem is that you're going to make it limp in the end."

"But, but last time yo—mmmmm!" The girl cut herself off with a moan, and a pregnant silence permeated through the kitchen for a moment or two. "That was gooood." Mercury glanced over to Emerald, whose only response was a wide-eyed expression.

"Hey, don't get greedy yet! You'll get more later when it's ready."

"Can't we just start it now?" the girl whined. "I'm getting hungry already!"

Hungry? This girl is quite forward, isn't she? "You know we can't start making this until we add the final ingredient."

"What do you mean?"

The male voice sighed. "You forgot to add the baking soda."

Wait, what? Mercury had slowly gotten suspicious about what was going on in the kitchen, but now he was genuinely baffled about how all this baking stuff was adding up. He just had to know, cover be damned. Without warning, Mercury burst through the door and found…

"…pancakes?"

The two former shadows leapt up upon Mercury's sudden remark. One of them was a stoic-looking guy with long black hair tied in a ponytail and caked with what he could only assume was flour. The other one was unmistakably the bubbly voice from earlier – for cryin' out loud, she's wearing a pink skirt and has a heart on her chest! She was the first one to break the temporary still.

"Yeah, and you can't have any!" she exclaimed defiantly, standing in between Mercury and a bowl brimming with batter.

"Nora, I don't think he's here for the pancakes," the boy stated evenly. He turned to face Mercury. "Though I suppose I am curious as to why you're here."

Emerald finally poked her head out to observe what all the commotion was about. Upon seeing the scene of the messy kitchen, she let out a breath of relief. "Oh, thank gods you were wrong."

The guy raised an inquisitive eyebrow. "Oh? What did you think we were doing?"

"It's not important, rea—"

"He thought you were having sex in the kitchen."

The Nora girl started acting all fidgety. "What, Ren and I? No, no, no, we're together, but not, like, together together, you know?" Uh huh, I believe that. "But, I mean, if I had to pick a place to do it, here wouldn't be so bad. Not that we'd actually do anything, 'cause we're just friends an—"

Ren covered Nora's mouth with a silencing finger. "You don't have to explain yourself, Nora. Anyway, the question still stands: what are you two doing down here in the middle of the night?"

"Says the guy breaking into the kitchen to make pancakes," Emerald retorted.

Mercury swore he didn't see the girl in pink move, but before he realized it, she was already poking through the bag he left on the floor. "Ooo, that's a lot of food you got here!"

Ren gave Emerald a nonplussed look, to which she lamely smiled. "Alright, we never saw you here."

"And I've never seen you before."

"Good." Satisfied, she spun about on her heels and faced the door. "Let's go, Merc."

"Right." He hoisted up his sack of food and slung it over his shoulder. With one last glance over to the strange pair, Mercury waved and said, "Have fun doing whatever you were doing. Or weren't doing."

Mercury and Emerald stepped back out into the dark hallway, ignoring Nora's cheerful goodbyes. Once outside, Emerald spoke up.

"Alright, it's official – Beacon is weird."

Cinder, as always, rose in the morning with grace. The morning sun lit her up in a warm glow, almost like an angel. She had a good night's sleep and was ready to bring the day into submission. Everything felt right in the world. However, something was off that particular morning…

Why are Mercury and Emerald still asleep?

Cinder thought that she had made it crystal clear that her minions would always wake up before she did so that she would never have to wait on them, yet the two of them were still sprawled out on their beds, still soundly asleep. More than that, they were still dressed in their uniforms from the day before – Mercury didn't even take his shoes off. Stranger still was how stuffed their backpacks were.

So, they went and nabbed something in the night? Cinder wondered. She didn't order them to do anything, so technically they were being insubordinate, but Cinder would chew them out later. For the moment, she was more curious as to what they decided to pilfer.

Upon opening Emerald's backpack, a number of cans, bars, and bags spilled out onto the floor, all filled with various foodstuffs. Cinder picked one of the bars with a label reading "Thrill of the Hunt Pro Bar: Now with 50% more Protein!" and gave a small shrug.

Not a hot breakfast, but it'll do, she thought as she peeled the wrapper off the bar and slipped back under the covers.

Good Lord, have I been shafted by exams lately. I'd been sitting on this for a while, but I've had exam after exam for the past two weeks (plus editing for Acceptance), so... well, doesn't matter, because here we are!

Merc never really said what his favorite smell is, but I'd reckon it'd be something along the lines of that new shoe smell. Because, y'know, Merc is all about that footwork and likes sniffin' boots? Somethin' like that.

Anyway, I'm still kinda exhausted, so this'll be the end of this little note. Catch ya next time!


In those moments of sufferance my heart was talking to God and it was praying: God, please, give me another chance! Today I live, I love life, I love all the people, I love everything that God has blessed but the most important thing is that: I love God! I will help everybody that need help and that are suffering as much as I can.

miercuri, 10 septembrie 2014

I want to live! This was my motto all my life.

I am 45 years old and in 1989 I have finished the Romanian Military School, I have became a fire ranger, my family legacy. From that moment I have loved this job more than anything in the world.At the 1989 Revolution I have participated in extinguishing fires and saving lives, my name being written with honor in the list with the Heroes of the Revolution.

Everything that I was doing was being done from the heart. I had no interest about the money or being praised. Never in my job, fires, water floods, or the earthquakes, I have never been afraid of the Death. God gave me so much courage that I have always been a winner.

In 20 years of work I have many diplomas and medals. They were making me happy but, at the same time, they were reflecting the passion for my job and the dedication for saving lives.

My personal life was in harmony with the military one. In 1995 I have married the person that I was in love with. After 2 years my boy was born. Everything was so beautiful.

After 6 years, from very vague reasons, I have divorced from my wife. According to the Romanian law, my boy stayed with his mother. I had my first shock from life. Before that moment my boy used to spend most of his time in the military barracks, among the soldiers, among the military trucks, eating with us, knowing the meaning of each alarm, wearing the military suit, etc. He was like a troupe boy.

Professionally everything was good. The Romanian President, Ion Iliescu, awarded me with the honor medal for special activities.

In 2009, I have made a routine control at the Ministry of Interiors’ Hospital from Bucharest because I was dealing with aggressive stomach pains. The doctors told me then that the pain came from a Non-Hodgkin malignant lymphoma.

In 14.09.2009 I have started the chemotherapy hoping that life will defeat death. As for the doctors, they told me that I have maximum 2 months of life.

God has disapproved the doctors and today I am alive even if I have made chemotherapy for almost two years, surgeries, bone marrow transplant at Fundeni Hospital, while losing the kindest person that life gave me: my mother.

At the Hematology Department, their psychiatrist was a big help to me. His advices, the daily encouragements and conciliation gave me hope and strength to fight.

The doctors considered that the background of my disease came from my emotional mood and it was accentuated by the heavy tasks of my military job, by the divorce, by the loss of my child in court and, the most important thing, by the daily stress.

I am sure that a good part of my healing comes from my faith in God. The other part comes from a group of hematologist doctors, surgeons, etc from Spitalul Universitar de Urgente Bucuresti, all of les led by a professional, my angel sent from God to heal people: The Chief of the Hematology Section, Professor Ana Maria Vladareanu. My patience and my faith, but the most important- my will to live, were thosethings that motivated me in each moment. Among me, I had all my family, my friends and all my neighbours.

My boy had to suffer one more time when he saw me how much I suffered and he was trying to heal my pain with his presence, with his words and with his most important will: Dad, I want to become the best handball player from Romania!The results started to show up quickly. My boy was national champion at the Handball Academy from Baia Mare between the years 2012-2014 and he won’t stop here, he will continue playing because he has potential.

I thank God for the disease he gave me. It helped me realize the reality and it helped me realize that the most important things on earth are the family and the health. These things will come if you have God in your soul. The money, the houses, the cars aren’t valuable against the disease and none of them can help you when you are sick.The charity is the weapon with which you can fight everything in life. Among the months spent by me in the hospital I have seen wealthy people suffering, tortured by severe illnesses but, at the end, they were all equal when facing the pain.

In those moments of sufferance my heart was talking to God and it was praying: God, please, give me another chance! Today I live, I love life, I love all the people, I love everything that God has blessed but the most important thing is that: I love God! I will help everybody that need help and that are suffering as much as I can.

I had a good collaboration with the doctors’ team from Spitalul Universitar Bucuresti, the Hematology Section, especially with their chief, Professor Doctor Ana Maria Vladareanu.

My income is not that big. I live in a small apartment with mortgage at the bank. I wish from all my heart to have friends from all the places in the world, to travel, to help all those in need and to be an example to them of: Life defeats death!

God, please listen my prayers and help me fulfill them!

There are a lot a ill people and if you can, let's help them all! It doesn't matter the country that you come from, the language that you speak, any disease of any nationality can bring sometimes death...

Despre mine

Arhivă blog

If you want me to show you my beautiful country, come and visit the black Sea, the Danube, the mountains with the Peles Castle or the Bran-Dracula Castle, to live one day in Maramures or Bucovina! I have all the time in the world but financially it’s not that easy…


Q:

Unable to Install Microsoft Azure Backup Server

I've been having a problem for the past two days trying install Microsoft Azure Backup Server... I'm very close.
The installation always fails to install the SQL server as shown in the image.
The error logs state:
On a domain controller, you cannot use the built-in Windows service accounts (Local Service or Network Service) as service accounts for Reporting Services

A:

Installation of Azure Backup Server on a domain controller is not supported - see this article.

I imagine this is primarily due to the reason you encountered, that installing SQL on a domain controller is also not supported. You will need to use another machine.


You are not alone!

customers served (give or take a few hundred thousand) since September 2004!

Comments and opinions expressed on THE KNIGHT SHIFT are those of Christopher Knight and not necessarily those of subjects discussed in this blog, of advertisers appearing on it or of any reasonable human being. Any correspondence/irate letters/lawsuit threats/Nigerian e-mail scams can be sent to theknightshift@gmail.com.

It took me an hour and a half after the episode aired on BBC America before I could turn in a blog post about "The Bells of Saint John"...

So along with statues, shadows, clocks, gas masks, cracks in the walls and Lord knows what else, now we have to be afraid of our Wi-Fi networks. Damn you Steven Moffat! DAMN YOU!!

(But he sure knows how to run Doctor Who like nobody's business, doesn't he?)

Three months after we last saw The Doctor (Matt Smith) in the 2012 Christmas special "The Snowmen", our hero is again sulking in solitude: this time at a monastery in England circa 1207. Considered mad by his fellow monks (not the first no doubt), we find the last Time Lord contemplating, perhaps obsessing, with the newest enigma of his long life: Clara Oswin (Jenna Louise-Coleman, in her first regular Doctor Who episode as a companion). When the telephone on the TARDIS's exterior starts ringing - by itself something which should not be happening - it isn't long before The Doctor is flying off again into time and space.

I'm not going to say anything else about "The Bells of Saint John", except that I thought it was a fairly strong return of both Doctor Who as a series as well as the start of an entirely new period of The Doctor's life. Jenna Louise-Coleman came to the show in this season's premiere episode "Asylum of the Daleks". "The Snowmen" made it clear in no uncertain terms that her character... or characters... is going to become a significant part of the series' mythology for the foreseeable future. "The Bells of Saint John" begins that next era in earnest. And judging by the myriad of sly references to previous material (hint: look at the author of that book) this promises... or threatens... to be a hella wild and scary ride in the lead-up to the big fiftieth anniversary of Doctor Who this fall.

A pretty solid episode, and one that continues the fine Moffat tradition of giving us something new to keep a watchful eye on. What's he gonna frighten us with next... vacuum cleaners? Fish and chips? Toilets?


Moby-Dick or, The Whale

“It is the horrible texture of a fabric that should be woven of ships’ cables and hawsers. A Polar wind blows through it, and birds of prey hover over it.”

So Melville wrote of his masterpiece, one of the greatest works of imagination in literary history. In part, Moby-Dick is the story of an eerily compelling madman pursuing an unholy war against a creature as vast and dangerous and unknowable as the sea itself. But more than just a novel of adventure, more than an encyclopaedia of whaling lore and legend, the book can be seen as part of its author’s lifelong meditation on America. Written with wonderfully redemptive humour, Moby-Dick is also a profound inquiry into character, faith, and the nature of perception.


Q:

h5py: how to read selected rows of an hdf5 file?

Is it possible to read a given set of rows from an hdf5 file without loading the whole file? I have quite big hdf5 files with loads of datasets, here is an example of what I had in mind to reduce time and memory usage:
#! /usr/bin/env python

import numpy as np
import h5py

infile = 'field1.87.hdf5'
f = h5py.File(infile,'r')
group = f['Data']

mdisk = group['mdisk'].value

val = 2.*pow(10.,10.)
ind = np.where(mdisk>val)[0]

m = group['mcold'][ind]
print m

ind doesn't give consecutive rows but rather scattered ones.
The above code fails, but it follows the standard way of slicing an hdf5 dataset. The error message I get is:
Traceback (most recent call last):
  File "./read_rows.py", line 17, in <module>
    m = group['mcold'][ind]
  File "/cosma/local/Python/2.7.3/lib/python2.7/site-packages/h5py-2.3.1-py2.7-linux-x86_64.egg/h5py/_hl/dataset.py", line 425, in __getitem__
    selection = sel.select(self.shape, args, dsid=self.id)
  File "/cosma/local/Python/2.7.3/lib/python2.7/site-packages/h5py-2.3.1-py2.7-linux-x86_64.egg/h5py/_hl/selections.py", line 71, in select
    sel[arg]
  File "/cosma/local/Python/2.7.3/lib/python2.7/site-packages/h5py-2.3.1-py2.7-linux-x86_64.egg/h5py/_hl/selections.py", line 209, in __getitem__
    raise TypeError("PointSelection __getitem__ only works with bool arrays")
TypeError: PointSelection __getitem__ only works with bool arrays

A:

I have a sample h5py file with:
data = f['data']
#  <HDF5 dataset "data": shape (3, 6), type "<i4">
# is arange(18).reshape(3,6)
ind=np.where(data[:]%2)[0]
# array([0, 0, 0, 1, 1, 1, 2, 2, 2], dtype=int32)
data[ind]  # getitem only works with boolean arrays error
data[ind.tolist()] # can't read data (Dataset: Read failed) error

This last error is caused by repeated values in the list.
But indexing with lists with unique values works fine
In [150]: data[[0,2]]
Out[150]:
array([[ 0,  1,  2,  3,  4,  5],
       [12, 13, 14, 15, 16, 17]])

In [151]: data[:,[0,3,5]]
Out[151]:
array([[ 0,  3,  5],
       [ 6,  9, 11],
       [12, 15, 17]])

So does an array with the proper dimension slicing:
In [157]: data[ind[[0,3,6]],:]
Out[157]:
array([[ 0,  1,  2,  3,  4,  5],
       [ 6,  7,  8,  9, 10, 11],
       [12, 13, 14, 15, 16, 17]])
In [165]: f['data'][:2,np.array([0,3,5])]
Out[165]:
array([[ 0,  3,  5],
       [ 6,  9, 11]])
In [166]: f['data'][[0,1],np.array([0,3,5])]
# errror about only one indexing array allowed

So if the indexing is right - unique values, and matching the array dimensions, it should work.
My simple example doesn't test how much of the array is loaded.  The documentation sounds as though elements are selected from the file without loading the whole array into memory.