text:
\section*{Introduction}\label{sec:intro}

A \emph{hypergraph} is a collection of subsets - called \emph{hyperedges} - of a finite ground set, and a \emph{transversal} is a subset of the ground set that intersects
every hyperedge.  In this paper, we consider the problem of counting the (inclusion-wise) minimal transversals of \emph{$\beta$-acyclic hypergraphs}. Counting problems
are usually harder than decision problems as for instance computing a (minimal) transversal of a hypergraph can be done in polynomial time while counting the number of
(minimal) transversals is $\#$P-complete \cite{Vadhan01}.  Informally, $\#$P denotes the set of functions corresponding to the number of accepting paths of a
non-deterministic Turing machine, and FP $\subseteq$ $\#$P, the set of functions computable in polynomial time. Under the assumption $\#$P $\ne$ FP, one may be interested
in classifying counting problems between those that are easy to compute, \emph{i.e.}\xspace, belong to FP, and those that are hard, \emph{i.e.}\xspace, are $\#$P-hard \cite{Valiant79}, or even hard to
approximate \cite{GoldbergGL16}.

The \textsc{Hypergraph Dualisation} problem -- a fifty years open problem -- asks for the enumeration of all (inclusion-wise) minimal transversals of a given hypergraph. It is not yet known whether this problem can be solved by an algorithm that runs in time polynomial in the size of the output despite the fact that it has been extensively studied since it has several applications in many areas such as graph theory, artificial intelligence, datamining, model-checking, network modeling, or databases (see the survey \cite{EiterGM08}). For all these applications, the minimality of the transversals is needed. Thus, even if it is not hard to see that listing all transversals of a hypergraph can be done with a polynomial delay between two solutions, there may be an exponential gap between the number of minimal transversals and the number of transversals (see for instance the non-trivial class of affine formulas), which makes efficient enumeration of minimal transversals much harder.

The problem of computing the number of minimal transversals of a hypergraph is closely related to the \textsc{Hypergraph Dualisation} problem and has also many applications in several areas, see for instance the description given in \cite{DurandH08} in the case of model checking. This problem has also applications in graph theory as it is closely related to the problem of counting the \emph{minimal dominating sets} of a graph. It turns out that these counting problems are $\#$P-complete in general, that is, it is very unlikely that it can be solved in polynomial time on every input.  However, there is a rich literature on solving this problem in polynomial time by restricting the input hypergraph to a specific class, see for example~\cite{CapelliPhd2016,KanteLMNU13,GolovachHKKSV17}.

 \paragraph{Our contributions and approach} In this paper, we follow this line of research by exhibiting a new tractable class of hypergraphs for this problem, namely, the class of $\beta$-acyclic hypergraphs.
 The \textsc{Hypergraph Dualisation} problem was already known to be tractable for this class~\cite{EiterG2002}.
 Moreover, it has been proved in \cite{Brault-BaronCM15} that the number of transversals of a $\beta$-acyclic hypergraph can be computed in polynomial time but the complexity of computing the number of minimal transversals was still unknown. More precisely, we prove the following theorem:

\begin{mtheorem}
  The number of minimal transversals of a $\beta$-acyclic hypergraph can be computed in polynomial time.
\end{mtheorem}

A direct consequence of our result is the following corollary concerning the counting of \emph{minimal dominating sets} in a subclass of chordal graphs, called \textit{strongly chordal} graphs.
\begin{mcorollary}
	The number of minimal dominating sets of a strongly chordal graph is computable in polynomial time.
\end{mcorollary}

Besides the polynomial time algorithm, the main contribution of this article is the modification of the framework considered in \cite{Capelli17} in order to count minimal
models.  The techniques used in \cite{KanteLMNU13,GolovachHKKSV17} are based on structural restrictions and as shown in \cite{Capelli17} cannot work for $\beta$-acyclic
hypergraphs.  Instead, Capelli showed in \cite{Capelli17} how to construct, from the elimination ordering of a $\beta$-acyclic hypergraph associated to a boolean formula,
a circuit whose satisfying assignments correspond to the models of the boolean formula.  Such circuits are known as \emph{decision Decomposable Negation Normal Form} in
knowledge compilation.  While the technique allows to count the models of non-monotone formulas, it cannot be used to count the minimal models.  Indeed, the branchings of
the constructed circuit do not allow to control the minimality.  We overcome this difficulty by introducing the notion of \emph{blocked transversals}, which correspond
roughly to the minimal transversals of a sub-hypergraph that are transversals of the whole hypergraph.  We then show that blocked transversals can be used to control the
minimality in the construction of the circuit.  However, this control is only possible in the case of monotone Boolean formulas, corresponding to counting the minimal
transversals of $\beta$-acyclic hypergraphs.

Because of technical definitions, we postpone the details of the algorithm in Section \ref{sec:algo}.  The paper is organised as follows. Notations and some technical
definitions are given in Section \ref{sec:def}, while \emph{blocked transversals} and intermediate lemmas are given in Section \ref{sec:blocked-tr}.  The decomposition of
$\beta$-acyclic hypergraphs proposed in \cite{Capelli17} is refined in Section \ref{sec:decbeta} to take into account \emph{blocked transversals}.  Finally, the algorithm
is given in Section \ref{sec:algo} and we talk about its consequences for the counting of minimal dominating sets in Section \ref{sec:dom}.

\section{Definitions and notations}
\label{sec:def}

 The power set of a set $V$ is denoted by $2^V$, and its cardinal is denoted by $\#V$. For two sets $A$ and $B$, we let $A\setminus B$ denote the set $\{x\in A\mid x\notin B\}$. For a ground set $V$ and subsets $\mathcal{A}_1,\ldots,\mathcal{A}_k$ of $2^V$, with $k\geq 2$, we let
\begin{align*}
  \bigotimes_{1\leq i\leq k} \mathcal{A}_i & := \begin{cases}  \emptyset  & \textrm{ if $\mathcal{A}_i=\emptyset$ for some $1\leq i \leq k$},\\
  	\{T_1\cup \dots \cup T_k \mid \forall i\leq k, \ T_i\in \mathcal{A}_i\}
    &\textrm{ otherwise}. \end{cases}
\end{align*}
If $k=2$, we write $\mathcal{A}_1\bigotimes \mathcal{A}_2$ as usual.
For example, if $\mathcal{A}_1=\{ \{a,b\}, \{ b,c\} \}$ and $\mathcal{A}_2=\{\{ d\}, \{e,f \}\}$, then $\mathcal{A}_1\bigotimes \mathcal{A}_2 = \{ \{ a,b,d  \}, \{a,b,e,f \}, \{ b,c,d \}, \{ b,c,e,f\} \}$.
\subsection{Hypergraphs}

A hypergraph $\mathcal{H}$ is a collection of subsets of a finite ground set. The elements of $\mathcal{H}$ are called the {\em hyperedges} of $\mathcal{H}$ and the {\em vertex set} of $\mathcal{H}$
is $V(\mathcal{H}) := \bigcup_{e \in \mathcal{H}} e$.

Given $S \subseteq V(\mathcal{H})$, we denote by $\mathcal{H}[S]$ the {\em hypergraph induced by $S$}, that is, $\mathcal{H}[S] := \{e \cap S \mid e \in \mathcal{H} \}$.  Any subset $\mathcal{H}'$ of
$\mathcal{H}$ is called a \emph{sub-hypergraph} of $\mathcal{H}$.
Observe that if there exists $e \in \mathcal{H}$ such that $e \subseteq V(\mathcal{H})\setminus S$, then $\emptyset \in \mathcal{H}[S]$. We do not enforce hypergraphs to have non-empty
edges or to be non-empty. However, a hypergraph with an empty edge may behave counter-intuitively. In the following definitions, we explicitly explain the extremal cases
where $\emptyset\in\mathcal{H}$ or $\mathcal{H} = \emptyset$.

Given a hypergraph $\mathcal{H}$ and a subset $S\subseteq V(\mathcal{H})$ of its vertex set, we denote by $\mathcal{H}(S)$ the set of hyperedges of $\mathcal{H}$ containing at least one vertex in $S$,
that is, $\mathcal{H}(S) := \{e \in \mathcal{H} \mid S\cap e\neq \emptyset\}$; to ease notations, we write $\mathcal{H}(x)$ instead of $\mathcal{H}(\{x\})$ for $x\in V(\mathcal{H})$.  Observe that $\mathcal{H}(x)$ is the set of hyperedges containing $x$.
For the hypergraph $\mathcal{H}$ shown in Figure \ref{fig:example}, $\mathcal{H}(\{d,x\})$ is the hypergraph $\{\{b,x\},\{c,x\},\{c,d\}\}$.

Given a hypergraph $\mathcal{H}$, a walk between two distinct edges $e_1$ and $e_k$ is a sequence $(e_1,x_1,e_2,x_2, \ldots, e_{k-1},x_{k-1},e_k)$ such that $x_i\in e_i\cap
e_{i+1}$ for all $1\leq i \leq k-1$. Notice that, $(e_k,x_{k-1},e_{k-1}, \ldots, x_2, e_2,x_1,e_1)$ is also a walk between $e_k$ and $e_1$. A maximal set of edges of
$\mathcal{H}$ that are pairwise connected by a walk is called a \emph{connected component} of $\mathcal{H}$. It is worth noticing that if $C_1,\ldots, C_k$ are the connected
components of $\mathcal{H}$, then $V(C_i)\cap V(C_j)=\emptyset$ for distinct $i,j$ in $\{1,\ldots, k\}$.

A hypergraph $\mathcal{H}$ is said \emph{$\beta$-acyclic} if there exists an ordering $x_1,\ldots, x_n$ of $V(\mathcal{H})$ such that for each $1\leq i \leq n$, the set
$\{e\cap \{x_i,\ldots,x_n\}\mid e\in \mathcal{H},\ x_i\in e\}$ is linearly ordered by inclusion. Such an ordering is called a \emph{$\beta$-elimination ordering}. It is well-known that every
sub-hypergraph $\mathcal{H}'$ of a $\beta$-acyclic hypergraph $\mathcal{H}$ are $\beta$-acyclic as well (see for instance \cite{EiterG95}).

\subsection{Transversals}
\label{sec:trans}

Let $\mathcal{H}$ be a hypergraph. A transversal for $\mathcal{H}$ is a subset $T \subseteq V(\mathcal{H})$ such that for every $e \in \mathcal{H}$, $T \cap e \neq \emptyset$.  We denote by
$\mathsf{tr}(\mathcal{H})$ the set of transversals of $\mathcal{H}$. Observe that if $\emptyset \in \mathcal{H}$, then $\mathsf{tr}(\mathcal{H}) = \emptyset$ as for every $T \subseteq V(\mathcal{H})$,
$\emptyset \cap T = \emptyset$ so $T$ cannot be a transversal of $\mathcal{H}$.  Finally, observe that if $\mathcal{H} = \emptyset$, then $\mathsf{tr}(\mathcal{H}) = \{\emptyset\}$.

A transversal $T$ of $\mathcal{H}$ is {\em minimal} if and only if for every $x \in T$, it holds that $T \setminus \{x\} \notin \mathsf{tr}(\mathcal{H})$. A hyperedge $e$ such that
$e \cap T = \{x\}$ is said to be {\em private for $x$ \emph{w.r.t.}\xspace $T$}. When $T$ is clear from the context, we may refer to such hyperedges as simply privates for $x$.  The following fact follows directly from the definitions:

\begin{fact}\label{fact:minT} $T$ is a minimal transversal of a hypergraph $\mathcal{H}$ if and only if $T$ is a transversal of $\mathcal{H}$ and each vertex $x\in T$ has a private.
\end{fact}

We denote by $\mathsf{mtr}(\mathcal{H})$ the set of minimal transversals of $\mathcal{H}$. Again, observe
that if $\mathcal{H} = \emptyset$ then $\mathsf{mtr}(\mathcal{H}) = \{\emptyset\}$.

Figure \ref{fig:example} depicts a hypergraph together with its minimal transversals.

\begin{figure}[!h]
	\centerline{\includegraphics[scale=0.95]{example.pdf}}
	\caption{A hypergraph $\mathcal{H}=\{ \{a,b\}, \{b,x \}, \{x,c\} ,\{c,d\}\}$ having $4$ minimal transversals. We have $\mathsf{mtr}(\mathcal{H})=\{ \{ a,x,d\}, \{a,x,c \}, \{b,x,d\}, \{b,c\} \}$.}
\label{fig:example}
\end{figure}

It is worth noticing that since the sets $\mathsf{tr}(\mathcal{H})$ and $\mathsf{mtr}(\mathcal{H})$ are sets of subsets of $2^{V(\mathcal{H})}$, they may be seen as hypergraphs on $V(\mathcal{H})$. Thus, we will sometimes use the notations $\mathsf{tr}(\mathcal{H})(S)$
(resp. $\mathsf{mtr}(\mathcal{H})(S)$) which refer to the transversals (resp. minimal transversals) $T$ of $\mathcal{H}$ such that $S \cap T \neq \emptyset$.

\section{Blocked transversals}\label{sec:blocked-tr}

Our algorithm uses a dynamic programming approach by finding a relation between the number of minimal transversals of a $\beta$-acyclic hypergraph  $\mathcal{H}$ with the number of minimal transversals of some specific subhypergraphs of $\mathcal{H}$. However, it is not possible to directly relate these quantities together. To illustrate this fact, let $\mathcal{H}$ be the hypergraph depicted in Figure \ref{fig:example}.  The minimal transversals of $\mathcal{H}$ containing $x$ are
$\{ a,x,c\}, \{a,x,d \}$ and $\{b,x,d \}$.  Observe that removing $x$ from these sets directly yields  a minimal transversal of
$\mathcal{H}\setminus \mathcal{H}(x)=\{\{a,b\} ,\{c,d\} \}$.  However, adding $x$ to a minimal transversal of $\mathcal{H}\setminus \mathcal{H}(x)$ does not give necessarily a minimal transversal of $\mathcal{H}$.
For example, we have $\{b,c\} \in \mathsf{mtr}(\mathcal{H}\setminus \mathcal{H}(x))$, but $\{b,x,c\} \notin \mathsf{mtr}(\mathcal{H})$.

In fact, we can show in general that $T\cup x \in \mathsf{mtr}(\mathcal{H})$ if and only if $T$ is a minimal transversal of $\mathcal{H}\setminus\mathcal{H}(x)$ and $T$ is not a transversal of $\mathcal{H}$.
Consequently, the number of minimal transversals of $\mathcal{H}$ containing $x$ is
\begin{align}\label{eq:1} \sharp \mathsf{mtr}(\mathcal{H}\setminus \mathcal{H}(x)) - \sharp (\mathsf{tr}(\mathcal{H})\cap \mathsf{mtr}(\mathcal{H}\setminus \mathcal{H}(x))). \end{align}
We can infer from this fact a recursive formula to compute $\sharp\mathsf{mtr}(\mathcal{H})$.
In the general case, using this formula as it is will lead to the computation of an exponential number of terms. In this section, we will make this relation more precise by introducing the notion of \emph{blocked transversal}. In the next section, we will show how we can use this relation to evaluate the number of minimal transversals of a $\beta$-acyclic hypergraphs  with only a polynomial number of intermediate values.

Given a hypergraph $\mathcal{H}$, a sub-hypergraph $\mathcal{H}' \subseteq \mathcal{H}$ and $B \subseteq V(\mathcal{H})$, we define the {\em $B$-blocked transversals} of $\mathcal{H}'$ to be
the transversals $T$ of $\mathcal{H}'$ such that each vertex $x$ of $T$ has a private in $\mathcal{H}' \setminus \mathcal{H}'(B)$.  In particular, if $y$ is a vertex of $B$,
then $y$ cannot be in a $B$-blocked transversal of $\mathcal{H}'$. Observe also that if $y \in V(\mathcal{H}) \setminus V(\mathcal{H}')$, then $y$ cannot be in a $B$-blocked
transversal of $\mathcal{H}'$.

\begin{fact}\label{fact:blocked} Given a sub-hypergraph $\mathcal{H}'$ of a hypergraph $\mathcal{H}$ and $B\subseteq V(\mathcal{H})$, $T$ is a $B$-blocked transversal of $\mathcal{H}'$ if and only if
  $T$ belongs to $\mathsf{tr}(\mathcal{H}')\cap \mathsf{mtr}(\mathcal{H}'\setminus \mathcal{H}'(B))$.
\end{fact}

\begin{proof} If $T$ is a transversal of $\mathcal{H}'$ such that each vertex $x$ of $T$ has a private in $\mathcal{H}'\setminus \mathcal{H}'(B)$, then $T\subseteq V(\mathcal{H}'\setminus \mathcal{H}'(B))$ and
  is a transversal of $\mathcal{H}'\setminus \mathcal{H}'(B)$. Thus by Fact \ref{fact:minT} $T$ is a minimal transversal of $\mathcal{H}'\setminus \mathcal{H}'(B)$.  Conversely, if $T$ is a minimal
  transversal of $\mathcal{H}'\setminus \mathcal{H}'(B)$, then by Fact \ref{fact:minT} each vertex $x$ has a private in $\mathcal{H}'\setminus \mathcal{H}'(B)$. If in addition it belongs to the set of
  transversals of $\mathcal{H}'$, then it is a $B$-blocked transversal of $\mathcal{H}'$ by definition.
\end{proof}

As an example, let $\mathcal{H}$ be the hypergraph depicted in Figure \ref{fig:example}, $\mathcal{H}'=\mathcal{H}$ and $B=\{x\}$. The only $B$-blocked transversal of $\mathcal{H}$ is
$\{b,c\}$. While $\{b,d\}$ is a minimal transversal of $\mathcal{H}\setminus \mathcal{H}(x)$, it is not a $B$-blocked transversal as the hyperedge $\{x,c\}$ does not intersect
$\{b,d\}$.

\medskip

We call the set $\mathcal{H}'(B)$ the {\em blocked hyperedges}. Intuitively, $\mathcal{H}'(B)$ is the set of hyperedges that cannot be used as privates in a transversal of
$\mathcal{H}'$. We denote by $\mathsf{btr}_{B}(\mathcal{H}')$ the set of $B$-blocked transversals of $\mathcal{H}'$. By Fact \ref{fact:blocked}, we have
\[ \mathsf{btr}_B(\mathcal{H}') := \mathsf{tr}(\mathcal{H}') \cap \mathsf{mtr}(\mathcal{H}'\setminus \mathcal{H}'(B)). \] Observe that by definition, $\mathsf{mtr}(\mathcal{H}) = \mathsf{btr}_\emptyset(\mathcal{H})$. Moreover, if
$\mathcal{H}(B) = \mathcal{H} \neq \emptyset$, then $\mathsf{btr}_{\mathcal{H}}(\mathcal{H}) = \emptyset$ as $\mathsf{mtr}(\emptyset) = \{\emptyset\}$ and $\emptyset \notin \mathsf{tr}(\mathcal{H})$.  When $B=\{x\}$,
we denote $\mathsf{btr}_B(\mathcal{H})$ by $\mathsf{btr}_x(\mathcal{H})$.

Given $S \subseteq V(\mathcal{H})$, we denote by $\mathsf{tr}(\mathcal{H},S) := \{T \in \mathsf{tr}(\mathcal{H}) \mid T \subseteq S \}$. We extend this notation to $\mathsf{mtr}$ and $\mathsf{btr}$ as well.  The
following summarises observations about blocked transversals.

\begin{fact}\label{fact:prop-blocked} Let $\mathcal{H}'$ be a sub-hypergraph of a hypergraph $\mathcal{H}$ and $B,S\subseteq V(\mathcal{H})$. Then,
  \begin{enumerate}
  \item $\mathsf{btr}_B(\mathcal{H}') = \mathsf{btr}_{B\cap V(\mathcal{H}')}(\mathcal{H}')$.
  \item $\mathsf{btr}_B(\mathcal{H}',S)=\mathsf{btr}_B(\mathcal{H}',S\setminusB)$.
  \item If $x\notin V(\mathcal{H}')$, then $\mathsf{btr}_B(\mathcal{H}',S)=\mathsf{btr}_B(\mathcal{H}',S\setminus\{x\})$.
  \end{enumerate}
\end{fact}

Let us briefly explain how $B$-blocked transversals will be used in computing $\#\mathsf{mtr}(\mathcal{H})$. One checks easily that
$\#\mathsf{mtr}(\mathcal{H}) = \#\mathsf{mtr}(\mathcal{H},V(\mathcal{H})\setminus \{x\}) + \#\mathsf{mtr}(\mathcal{H})(x)$. By Equation \ref{eq:1}, $\#\mathsf{mtr}(\mathcal{H})(x)=\#\mathsf{mtr}(\mathcal{H}\setminus \mathcal{H}(x)) - \#\mathsf{btr}_x(\mathcal{H})$.  Therefore,
$\#\mathsf{mtr}(\mathcal{H}) = \#\mathsf{btr}_\emptyset(\mathcal{H}) = \#\mathsf{btr}_\emptyset(\mathcal{H},V(\mathcal{H})\setminus \{x\}) + \#\mathsf{btr}_\emptyset(\mathcal{H}\setminus \mathcal{H}(x)) - \#\mathsf{btr}_x(\mathcal{H})$. We will show in the next
section that we can define, from the $\beta$-elimination ordering of a $\beta$-acyclic hypergraph $\mathcal{H}$, sub-hypergraphs $\mathcal{H}_1, \ldots, \mathcal{H}_q\subseteq \mathcal{H}$ and vertices
$x_1,\ldots,x_q$ such that, for all $1\leq i \leq q$, $\#\mathsf{btr}_{x_i}(\mathcal{H}_i)$ and $\#\mathsf{btr}_\emptyset(\mathcal{H}_i)$ can be computed in polynomial time if $\#\mathsf{btr}_{x_j}(\mathcal{H}_j)$ and
$\#\mathsf{btr}_\emptyset(\mathcal{H}_j)$ are known for all $j< i$. As a consequence, one can compute $\#\mathsf{mtr}(\mathcal{H})$ by classical dynamic programming for any $\beta$-acyclic
hypergraph.

The end of this section is dedicated to the proof of several crucial lemmas concerning recursive formulas for computing the number of blocked transversals, and that will
be useful in our algorithm. We start by describing the blocked transversals of a hypergraph having more than one connected component.

\begin{lemma}
  \label{lem:btrcc} Let $\mathcal{H}$ be a hypergraph, $S,B \subseteq V( \mathcal{H})$ and $C_1,\ldots,C_k$ the connected components  of $\mathcal{H}[S]$. For each $i\in[1,k]$, let $\mathcal{H}_i=\{e\in\mathcal{H} \mid e\cap S\in C_i \}$. We have:
\[ \mathsf{btr}_B(\mathcal{H},S) = \bigotimes_{i=1}^k \mathsf{btr}_{B}(\mathcal{H}_i,S).\]
\end{lemma}
\begin{proof}
  Assume that $\emptyset \in \mathcal{H}[S]$, it means that there exists a hyperedge $e\in\mathcal{H}$ such that $e\cap S=\emptyset$. In this case, $\mathsf{btr}_B(\mathcal{H},S)=\emptyset$. Moreover, there exists
  $i\in [1,k]$ such that $C_i=\{\emptyset\}$ and $e\in\mathcal{H}_i$. Thus, $\mathsf{btr}_{B}(\mathcal{H}_i,S)=\emptyset$ and the equality holds in this case.

  Assume from now that $\emptyset\notin \mathcal{H}[S]$.  Let $T \in \mathsf{btr}_B(\mathcal{H},S)$. We show that for all $i \leq k$, $T_i = T \cap V(\mathcal{H}_i) \in \mathsf{btr}_{B}(\mathcal{H}_i,S)$. Let $e \in \mathcal{H}_i$. Since
  $e \in \mathcal{H}$, we have $e\cap T \neq \emptyset$.  As $e\in\mathcal{H}_i$, we have $e \subseteq V(\mathcal{H}_i)$.  Thus $e\cap T_i\neq \emptyset$, that is, $T_i \in \mathsf{tr}(\mathcal{H}_i,S)$.  Moreover, let $y \in T_i$.
  By definition of $T$, there exists $e \in \mathcal{H} \setminus \mathcal{H}(B)$ such that $e$ is private for $y$ \emph{w.r.t.}\xspace $T$. Observe that we have $T_i\subseteq S \cap V(\mathcal{H}_i) = V(C_i)$ since
  $T\subseteq S$. Thus, $y\in V(C_i)$ and $e\cap S \in C_i$, because $C_i$ is a connected component. We can conclude that $e\in \mathcal{H}_i$ and $e$ is private to $y$ \emph{w.r.t.}\xspace $T_i$ and
  $\mathcal{H}_i \setminus \mathcal{H}(B) = \mathcal{H}_i \setminus \mathcal{H}_i(B)$. Thus $T_i$ is a minimal transversal of $\mathcal{H}_i \setminus \mathcal{H}_i(B)$. That is $T_i \in \mathsf{btr}_{B}(\mathcal{H}_i,S)$.

  Now let $T_1 \in \mathsf{btr}_{B}(\mathcal{H}_1,S), \ldots, T_k \in \mathsf{btr}_{B}(\mathcal{H}_k,S)$.  We show that $T = \bigcup_{i=1}^k T_i \in \mathsf{btr}_B(\mathcal{H},S)$.  Let $e \in \mathcal{H}$. As
  $\mathcal{H} = \bigcup_{i=1}^k \mathcal{H}_i$, there exists $i$ such that $e \in \mathcal{H}_i$.  Thus $e \cap T_i \neq \emptyset$ and thus $e \cap T \neq \emptyset$, that is, $T \in \mathsf{tr}(\mathcal{H})$. It remains to show
  that $T\in\mathsf{mtr}(\mathcal{H}\setminus \mathcal{H}(B))$. Let $y \in T$.  By definition of $T$, there exists $i$ such that $y \in T_i$.  Thus, there exists $e \in \mathcal{H}_i \setminus \mathcal{H}_i(B)$ that is
  private for $y$ \emph{w.r.t.}\xspace $T_i$.  Moreover, since $\mathcal{H}_i(B) = \mathcal{H}_i \cap \mathcal{H}(B)$, we know that $e \notin \mathcal{H}(B)$.  As $C_1,\dots,C_k$ are the connected component of $\mathcal{H}[S]$, we
  have that, for every $j \neq i$, $V(C_i)\cap V(C_j)=\emptyset$. Moreover, for all $\ell \leq k$, we have $S\cap V(\mathcal{H}_\ell)=V(C_\ell)$. As $e\subseteq V(\mathcal{H}_i)$ and
  $T_j\subseteq S \cap V(\mathcal{H}_j)$, we have for every $j\neq i$:
  \[  e \cap T_j\subseteq V(\mathcal{H}_i)\cap S\cap V(\mathcal{H}_j) = V(C_i)\cap V(C_j)=\emptyset. \]
  Thus, $e\cap T = e \cap T_i = \{y\}$. In other words, $e$ is private for $y$ \emph{w.r.t.}\xspace $T$ and $\mathcal{H} \setminus \mathcal{H}(B)$. That is $T\in \mathsf{btr}_{B}(\mathcal{H})$.
\end{proof}

We recall that $\mathsf{btr}_B(\mathcal{H},S)(x)$ is the set of $B$-blocked transversals $T$ of $\mathcal{H}$ such that $T\subseteq S$ and $x\in T$. The following lemma shows that for any
$B$-blocked transversal $T\subseteq S$ of $\mathcal{H}$ containing $x$, we have $T\setminus x$ is a $B$-blocked transversal of $\mathcal{H}\setminus \mathcal{H}(x)$.

\begin{lemma}
\label{lem:btrinc}
  Let $\mathcal{H}$ be a hypergraph, $S,B \subseteq V(\mathcal{H})$ and $x \in S$.
  We have \[\mathsf{btr}_B(\mathcal{H},S)(x) \subseteq \{\{x\}\} \bigotimes \mathsf{btr}_{B}(\mathcal{H}\setminus \mathcal{H}(x),S\setminus\{x\}).\]
\end{lemma}
\begin{proof} Let $\mathcal{H}_1 := \mathcal{H} \setminus \mathcal{H}(x)$.  Let $T \in \mathsf{btr}_B(\mathcal{H},S)(x)$. By definition, $x \in T$ and $T\subseteq S$, thus we only have to show that
  $T' = T \setminus \{x\} \in \mathsf{btr}_{B}(\mathcal{H}_1)$. Let $e \in \mathcal{H} \setminus \mathcal{H}(x)$. Since $T$ is a transversal of $\mathcal{H}$, there exists $y \in e \cap T$.
  Moreover, by definition, $x \notin e$, thus $y \in T'$, that is, $T'$ is a transversal of $\mathcal{H} \setminus \mathcal{H}(x)$. It remains to show that $T'$ is a minimal
  transversal of $\mathcal{H}_1\setminus \mathcal{H}_1(B) = \mathcal{H} \setminus (\mathcal{H}(B) \cup \mathcal{H}(x))$. Let $y \in T'$. Since $T$ is a minimal transversal of
  $\mathcal{H} \setminus \mathcal{H}(B)$, there exists $e \in \mathcal{H} \setminus \mathcal{H}(B)$ such that $e$ is private for $y$ \emph{w.r.t.}\xspace $T$. Since $x \in T$, we have $x \notin e$,
  otherwise $e$ would not be private for $y$ \emph{w.r.t.}\xspace $T$. Thus $e \in \mathcal{H} \setminus (\mathcal{H}(B) \cup \mathcal{H}(x))$, that is, $e$ is private to $y$ \emph{w.r.t.}\xspace $T'$ in
  $\mathcal{H}_1\setminus \mathcal{H}_1(B)$. In other words, $T'$ is a minimal transversal of $\mathcal{H}_1\setminus \mathcal{H}_1(B)$ which concludes the proof.
\end{proof}

To complete the previous lemma, we show that for each $B$-blocked transversal $T\subseteq S$ of $\mathcal{H}\setminus\mathcal{H}(x)$, we have $T\cup \{x\}$ is a $B$-blocked transversal
of $\mathcal{H}$ if and only if $T$ is not a $(B\cup \{x\})$-blocked transversal of $\mathcal{H}\setminus (\mathcal{H}(B)\cap \mathcal{H}(x))$.

\begin{lemma}
\label{lem:btreq}
  Let $\mathcal{H}$ be a hypergraph, $S,B \subseteq V(\mathcal{H})$ and $x \in S$. We have
  \[ \big(\{\{x\}\} \bigotimes \mathsf{btr}_{B}(\mathcal{H}_1,S\setminus\{x\})\big) \setminus \mathsf{btr}_{B}(\mathcal{H},S)(x) = \{\{x\}\} \bigotimes \mathsf{btr}_{B \cup \{x\}}(\mathcal{H}_2,S\setminus\{x\})  \] where
 $\mathcal{H}_1 := \mathcal{H} \setminus \mathcal{H}(x)$ and $\mathcal{H}_2 := \mathcal{H} \setminus (\mathcal{H}(B) \cap \mathcal{H}(x))$.
\end{lemma}

\begin{proof} We prove the lemma by proving first the left-to-right inclusion (Claim~\ref{clm:lir}) and then the right-to-left inclusion (Claim~\ref{clm:ril}). But first,
  notice that $\mathcal{H}_1\setminus\mathcal{H}_1(B)=\mathcal{H}_2\setminus\mathcal{H}_2(B \cup \{x\})=\mathcal{H}\setminus(\mathcal{H}(B)\cup \mathcal{H}(x))$ since
  $\mathcal{H}(B)\cup\mathcal{H}(x)=\mathcal{H}(B\cup\{x\})$.

\begin{claim}
\label{clm:lir}
For every $T \in \big(\{\{x\}\} \bigotimes \mathsf{btr}_{B}(\mathcal{H}_1,S\setminus\{x\})\big) \setminus \mathsf{btr}_{B}(\mathcal{H},S)(x)$, we have $ T \setminus \{x\} \in \mathsf{btr}_{B \cup \{x\}}(\mathcal{H}_2,S\setminus\{x\})$.
\end{claim}
\begin{proof}
  We start by proving that $T' =T\setminus \{x\}$ is in $\mathsf{tr}(\mathcal{H}_2)$. Assume towards a contradiction that $T'\notin \mathsf{tr}(\mathcal{H}_2)$, \emph{i.e.}\xspace, there exists $e \in \mathcal{H}_2$
  such that $e\cap T'=\emptyset$. We prove that it implies $T \in \mathsf{btr}_B(\mathcal{H},S)(x)$.  First, observe that $T\in \mathsf{tr}(\mathcal{H})$, since
  $T'\in \mathsf{tr}(\mathcal{H}_1)=\mathsf{tr}(\mathcal{H}\setminus\mathcal{H}(x))$ and $T=T'\cup \{x\}$.  Thus, we have $e\cap T=\{x\}$ and $e\in\mathcal{H}(x)$. As
  $e\in\mathcal{H}_2=\mathcal{H}\setminus (\mathcal{H}(B)\cap \mathcal{H}(x))$, we have $e\in \mathcal{H}\setminus\mathcal{H}(B)$ and then $e$ is a private hyperedge for $x$ \emph{w.r.t.}\xspace $T$ and
  $\mathcal{H}\setminus\mathcal{H}(B)$.  Furthermore, every vertex in $T'$ has a private hyperedge \emph{w.r.t.}\xspace $T'$ and
  $\mathcal{H}_1\setminus\mathcal{H}_1(B)=\mathcal{H}\setminus(\mathcal{H}(B)\cup \mathcal{H}(x))$ since $T'\in \mathsf{mtr}(\mathcal{H}_1\setminus\mathcal{H}_1(B))$.  Thus, every vertex in $T'$ has a private
  hyperedge \emph{w.r.t.}\xspace $T$ and $\mathcal{H}\setminus\mathcal{H}(B)$.  As $T\in\mathsf{tr}(\mathcal{H})$, we can conclude that $T\in\mathsf{mtr}(\mathcal{H}\setminus\mathcal{H}(B))$.  Finally, we have
  $T \subseteq S$ by assumption. Therefore $T \in \mathsf{btr}_B(\mathcal{H},S)(x)$ which is a contradiction. Thus, $T'\in \mathsf{tr}(\mathcal{H}_2)$.

We now prove that $T' \in \mathsf{mtr}(\mathcal{H}_2 \setminus \mathcal{H}_2(B \cup \{x\}))$, that is, we prove the minimality of $T'$ in $\mathcal{H}_2 \setminus \mathcal{H}_2(B \cup \{x\})$. Let $y \in T'$. Since $T \in \mathsf{btr}_{B}(\mathcal{H}_1)$, there exists $f \in \mathcal{H}_1 \setminus \mathcal{H}_1(B)$ such that $f \cap T = \{y\}$. Since $\mathcal{H}_1 \setminus \mathcal{H}_1(B) = \mathcal{H}_2\setminus \mathcal{H}_2(B \cup \{x\})$, every $y \in T'$ have a private hyperedge in $\mathcal{H}_2 \setminus \mathcal{H}_2(B \cup \{x\})$, that is $T' \in \mathsf{mtr}(\mathcal{H}_2 \setminus \mathcal{H}_2(B \cup \{x\}))$. As $T'\subseteq S\setminus\{x\}$, we can conclude that $T'\in \mathsf{btr}_{B \cup \{x\}}(\mathcal{H}_2,S\setminus\{x\})$.
\end{proof}
\begin{claim}
\label{clm:ril}
For every $T \in \{x\} \bigotimes \mathsf{btr}_{B \cup \{x\}}(\mathcal{H}_2,S\setminus\{x\})$, we have
$T \in \{x\} \bigotimes \mathsf{btr}_{B}(\mathcal{H}_1,S\setminus\{x\}) \setminus \mathsf{btr}_{B}(\mathcal{H},S)(x)$.
\end{claim}

\begin{proof} We start by proving that $T' = T \setminus \{x\}$ is in $\mathsf{btr}_{B}(\mathcal{H}_1,S\setminus\{x\})$. First, we show that $T'$ is a transversal of $\mathcal{H}_1$. Let
  $e \in \mathcal{H}_1$. By definition of $\mathcal{H}_1$, $x \notin e$, thus $e \in \mathcal{H}_2$ as well. Therefore $e \cap T' \neq \emptyset$.  We now prove that $T'$ is minimal in
  $\mathcal{H}_1 \setminus \mathcal{H}_1(B)$. As $T'\in\mathsf{mtr}(\mathcal{H}_2\setminus\mathcal{H}_2(B \cup \{x\}))$, every vertex in $T'$ has a private hyperedge in
  $\mathcal{H}_2\setminus\mathcal{H}_2(B \cup \{x\})$. Moreover, recall that $\mathcal{H}_2\setminus\mathcal{H}_2(B \cup \{x\})=\mathcal{H}_1\setminus\mathcal{H}_1(B)$. Thus, $T'$ is minimal in
  $\mathcal{H}_1 \setminus \mathcal{H}_1(B)$. As $T'\subseteq S\setminus\{x\}$, we have $T'\in \mathsf{btr}_{B}(\mathcal{H}_1,S\setminus \{x\})$.

We finish the proof by showing that $T \notin \mathsf{btr}_B(\mathcal{H},S)(x)$. In order to prove it, we show that there is no private hyperedge for $x$ \emph{w.r.t.}\xspace $T$ and $\mathcal{H} \setminus
\mathcal{H}(B)$. Indeed, since $T'\in\mathsf{tr}(\mathcal{H}_2)$, every hyperedge in $\mathcal{H}_2$ contains a vertex in $T'$. By definition of $\mathcal{H}_2$, we have $\mathcal{H} \setminus
\mathcal{H}(B)\subseteq\mathcal{H}_2$, thus for every hyperedge $e$ in $\mathcal{H} \setminus \mathcal{H}(B)$, we have $e\cap T \neq \{x\}$, \emph{i.e.}\xspace, $e$ is not a private for $x$.
\end{proof}

By Claim \ref{clm:lir}  and Claim \ref{clm:ril} we can conclude the lemma.
\end{proof}

Finally, we characterise the number of $B$-blocked transversals of a hypergraph that do not contain a given vertex. We use the symbol $\uplus$ for the disjoint union of
sets.
\begin{lemma}
  \label{lem:btrnotx} Let $\mathcal{H}$ be a hypergraph, $S,B \subseteq V(\mathcal{H})$ and $x \in S$. We have
  \[ \mathsf{btr}_{B}(\mathcal{H},S) = \mathsf{btr}_{B}(\mathcal{H},S)(x) \uplus  \mathsf{btr}_{B}(\mathcal{H}, S\setminus\{x\}). \]
\end{lemma}

\begin{proof} Let $T\subseteq S$ be a $B$-blocked transversal of $\mathcal{H}$. Thus, either $x\in T$ and then $T\in \mathsf{btr}_B(\mathcal{H},S)(x)$, or $x\notin T$ and then $T\subseteq
  S\setminus \{x\}$, \emph{i.e.}\xspace, $T\in \mathsf{btr}_B(\mathcal{H},S\setminus \{x\})$. Since, the two cases are exclusive, we can conclude that $\mathsf{btr}_B(\mathcal{H},S)$ is the disjoint union of
  $\mathsf{btr}_B(\mathcal{H},S)(x)$ and of $\mathsf{btr}_B(\mathcal{H},S\setminus \{x\})$.
\end{proof}

A direct consequence of Lemma~\ref{lem:btrinc}, Lemma~\ref{lem:btreq} and Lemma~\ref{lem:btrnotx} is the
following equality characterising the number of $B$-blocked transversals of $\mathcal{H}$.  This will be a crucial step in our dynamic programming scheme.

\begin{theorem}
\label{thm:inductivestep}
Let $\mathcal{H}$ be a hypergraph, $S,B \subseteq V(\mathcal{H})$ and $x \in S$. We have
\[ \#\mathsf{btr}_{B}(\mathcal{H},S) = \#\mathsf{btr}_{B}(\mathcal{H},S\setminus\{x\}) + \#\mathsf{btr}_{B}(\mathcal{H}_1,S\setminus\{x\}) - \#\mathsf{btr}_{B \cup \{x\}}(\mathcal{H}_2,S\setminus\{x\}) \]
where $\mathcal{H}_1 := \mathcal{H} \setminus \mathcal{H}(x)$ and $\mathcal{H}_2 := \mathcal{H} \setminus (\mathcal{H}(B) \cap \mathcal{H}(x))$.
\end{theorem}

\begin{proof} By Lemma \ref{lem:btrnotx}, $\#\mathsf{btr}_{B}(\mathcal{H},S) = \#\mathsf{btr}_{B}(\mathcal{H},S\setminus\{x\}) + \#\mathsf{btr}_{B}(\mathcal{H},S)(x)$. By Lemma \ref{lem:btrinc} and
  Lemma \ref{lem:btreq}, $\{\{x\}\}\otimes \mathsf{btr}_B(\mathcal{H}_1,S\setminus \{x\}) = \mathsf{btr}_B(\mathcal{H},S)(x)\uplus \{\{x\}\}\otimes \mathsf{btr}_{B\cup \{x\}}(\mathcal{H}_2,S\setminus \{x\})$. Hence,
  $\#\mathsf{btr}_B(\mathcal{H},S)(x) = \#\mathsf{btr}_B(\mathcal{H}_1,S\setminus \{x\}) - \#\mathsf{btr}_{B\cup \{x\}}(\mathcal{H}_2,S\setminus \{x\})$. Therefore, the claimed equality holds.
\end{proof}

\section{Counting the minimal transversals of $\beta$-acyclic hypergraphs}
\label{sec:count}

In this section, we fix $\mathcal{H}$ a $\beta$-acyclic hypergraph, $\leq$ a $\beta$-elimination ordering of its vertices and we let $\leq_\mathcal{H}$ the induced lexicographic
ordering on the hyperedges, \emph{i.e.}\xspace, $e\leq_{\mathcal{H}} f$ if $\min((e\setminus f)\cup (f\setminus e))\in e$.  We denote by $\mathcal{H}_e^x$ the sub-hypergraph of $\mathcal{H}$ formed by the
hyperedges $f \in \mathcal{H}$ such that there exists a walk from $f$ to $e$ going only through hyperedges smaller than $e$ and vertices smaller than $x$. For an example, take
the $\beta$-elimination ordering $a,b,x,c,d$ of the hypergraph in Figure \ref{fig:example} and the induced ordering $\{a,b\}, \{b,x\},\{x,c\},\{c,d\}$ on $\mathcal{H}$. For
$e=\{x,c\}$, the hypergraph $\mathcal{H}_e^x$ is composed of the hyperedges $\{b,x\}$ and $\{x,c\}$.

For a vertex $x$ of $V(\mathcal{H})$, we write $[\leq x]$, $[< x]$ and $[\geq x]$ for, respectively, $\{y \in V(\mathcal{H}) \mid y \leq x\}$, $\{y \in V(\mathcal{H}) \mid y \leq x \wedge
y\neq x\}$ and $\{y \in V(\mathcal{H}) \mid x \leq y\}$. Moreover, we write $\mathcal{H}[\leq x]$, $\mathcal{H}[< x]$ and $\mathcal{H}[\geq x]$ instead of, respectively, $\mathcal{H}\big[[\leq x]\big]$,
$\mathcal{H}\big[[< x]\big]$ and $\mathcal{H}\big[[\geq x]\big]$.

\subsection{Decomposition of $\beta$-acyclic hypergraphs}
\label{sec:decbeta}

 The following two lemmas have been proven in~\cite[Section III-A]{Capelli17}.

\begin{lemma}[Theorem 3 in \cite{Capelli17}]
  \label{lem:hexvar} For every hyperedge $e \in \mathcal{H}$, and $x \in V(\mathcal{H})$, we have $V(\mathcal{H}_e^x) \cap [\geq x] \subseteq e$.
\end{lemma}
\begin{lemma}[Lemma 2 in \cite{Capelli17}]
  \label{lem:hexinc} Let $e$ and $f$ be two hyperedges of $\mathcal{H}$ such that $e \leq_\mathcal{H} f$, and let $x$ and $y$ be vertices of $\mathcal{H}$ such that $x \leq y$. If
  $V(\mathcal{H}_e^x) \cap V(\mathcal{H}_f^y) \cap [\leq x] \neq \emptyset$, then $\mathcal{H}_e^x \subseteq \mathcal{H}_f^y$.

\end{lemma}

We prove a lemma on the decomposition of $\mathcal{H}_e^x$ graphs that will be used with Lemma \ref{lem:btrcc} to propagate the dynamic programming algorithm.

\begin{lemma}
	\label{lem:betadecompo}
	Let $x\in V(\mathcal{H})$, $e \in \mathcal{H}$ and $S \subseteq [\geq x]$. Let
        \begin{align*}
\mathcal{H}' &:= \begin{cases} \mathcal{H}_e^x & \textrm{if $S = \emptyset$},\\  \mathcal{H}_e^x \setminus \left(\bigcap_{w\in
          S}\mathcal{H}_e^x(w)\right) & \textrm{otherwise}. \end{cases}
        \end{align*}
        For every connected component $C$ of $\mathcal{H}'[<x]$ different from $\{\emptyset\}$, there exists $y < x$ and $f \leq_\mathcal{H} e$ such that $C = \mathcal{H}_{f}^y[\leq y]$
        and $\mathcal{H}_f^y=\{g\in \mathcal{H}' \mid g\cap [<x] \in C \}$.
\end{lemma}

\begin{proof}
	 Let $y = \max(V(C))$ and $f = \max\{g\in \mathcal{H}' \mid g\cap [<x] \in C \}$.  We show that $\mathcal{H}_f^y=\{g\in \mathcal{H}' \mid g\cap [<x] \in C \}$.

         First, we observe that $\mathcal{H}_f^y\subseteq \mathcal{H}'$. If $S=\emptyset$, it follows from Lemma~\ref{lem:hexinc} because, in this case, $\mathcal{H}'=\mathcal{H}_e^x$. Suppose
         that $S\neq \emptyset$, by definition of $\mathcal{H}'$, we have $S\nsubseteq f$. Moreover, by Lemma~\ref{lem:hexvar}, we have that
         $V(\mathcal{H}_f^y)\cap [\geq y] \subseteq f$. As $S\subseteq [\geq x]$ and $x>y$, we have $S\subseteq [\geq y]$. Thus $S\nsubseteq V(\mathcal{H}_f^y)$ and for all
         $g\in \mathcal{H}_f^y$, we have $S\nsubseteq g$ since $g\subseteq V(\mathcal{H}_f^y)$. We can conclude that $\mathcal{H}_f^y\subseteq \mathcal{H}'$.

	Now, we prove that every $g\in \mathcal{H}_f^y$, we have $g \cap [<x] \in C$.
 Let $g\in \mathcal{H}_f^y$. By definition of $\mathcal{H}_f^y$ and because $\mathcal{H}_f^y\subseteq \mathcal{H}'$, there exists a path $P$ from $f$ to $g$ going only through vertices smaller than $y$ and hyperedges smaller than $f$ in $\mathcal{H}'$. As $y<x$, we can conclude that $f\cap[<x]$ is connected to $g\cap [<x]$ in $\mathcal{H}'$, \emph{i.e.}\xspace, $g \cap [<x] \in C$.
	In other words, we have $\mathcal{H}_f^y \subseteq \{g\in \mathcal{H}' \mid g\cap [<x] \in C \}$.

	It remains to prove the other inclusion. Let $g \in \mathcal{H}'$ with $g\cap [<x] \in C$. Since $C$ is a connected component of $\mathcal{H}'[<x]$, there exists a path $P$ from $f\cap [<x]$ to $g\cap[<x]$. By the maximality of $y$ and $f$, $P$ goes only through vertices smaller than $y$ and hyperedges smaller than $f$. We can construct from $P$ a path $P'$ from $f$ to $g$ in $\mathcal{H}'$ going through vertices smaller than $y$ and hyperedges smaller than $f$. As $\mathcal{H}'\subseteq \mathcal{H}$, we can conclude that $g\in\mathcal{H}_f^y$ and thus, $\mathcal{H}_f^y=\{g\in \mathcal{H}' \mid g\cap [<x] \in C \}$.
	Finally, observe that $C =\mathcal{H}_f^y[<x]= \mathcal{H}_{f}^y[\leq y]$ since $y=\max(V(C))$.
\end{proof}

\subsection{The algorithm}
\label{sec:algo}

In this subsection, we describe the dynamic programming algorithm we use to count the number of minimal transversals of a $\beta$-acyclic hypergraph.  We denote by $x_1$ the smallest element of $\leq$.

Our goal is to compute $\#\mathsf{btr}_\emptyset(\mathcal{H}_e^x,[\leq x])$ and $\#\mathsf{btr}_w(\mathcal{H}_e^x,[\leq x])$ for every $e \in \mathcal{H}$, $x \in V(\mathcal{H})$ and $w \in V(\mathcal{H})$ such that
$x < w$. Observe that it is enough for computing the number of minimal transversals of $\mathcal{H}$ as $\#\mathsf{mtr}(\mathcal{H}) = \#\mathsf{btr}_\emptyset(\mathcal{H}_{e_m}^{x_n},[\leq x_n])$
where $e_m$ is the maximal hyperedge for $\leq_\mathcal{H}$ and $x_n$ is the maximal vertex for $\leq$. Indeed, we have $\mathcal{H}_{e_m}^{x_n} = \mathcal{H}$ and $[\leq x_n]=V(\mathcal{H})$, thus
$\mathsf{btr}_\emptyset(\mathcal{H}_{e_m}^{x_n},[\leq x_n]) = \mathsf{btr}_\emptyset(\mathcal{H}) = \mathsf{mtr}(\mathcal{H})$.

The propagation of the dynamic programming works as follows: we use Theorem~\ref{thm:inductivestep} to reduce the computation of $\#\mathsf{btr}_B(\mathcal{H}_e^x,[\leq x])$ to the
computation of $\#\mathsf{btr}$ for several hypergraphs that do not contain $x$. We then use Lemma~\ref{lem:betadecompo} to show that these hypergraphs can be decomposed into
disjoint hypergraphs of the form $\mathcal{H}_f^y$ for $f \leq_\mathcal{H} e$ and $y < x$ which allows us to compute $\#\mathsf{btr}_B(\mathcal{H}_e^x,[\leq x])$ from precomputed values of the
form $\#\mathsf{btr}_{B'}(\mathcal{H}_f^y,[\leq y])$, where $B'\in \{B, \{x\}\}$.

Before continuing, let us give a high-level description of the algorithm. For each $1\leq i \leq n$ and each $1\leq j\leq m$, let $tab[i,j,0]$ be
$\#\mathsf{btr}_\emptyset(\mathcal{H}_{e_j}^{x_i},[\leq x_i])$, and for each $\ell>i$, let $tab[i,j,\ell]$ be $\#\mathsf{btr}_{x_\ell}(\mathcal{H}_{e_j}^{x_i},[\leq x_i])$. Because the number of minimal
transversals of $\mathcal{H}$ is $\#\mathsf{btr}_\emptyset(\mathcal{H}_{e_m}^{x_n},[\leq x_n])$, it is enough to show how to compute $tab[n,m,0]$ in polynomial time. The following is a high
level description of the algorithm which computes $tab[i,j,\ell]$, for all $1\leq i\leq n$, $1\leq j\leq m$ and $\ell\in \{0,i+1,\ldots,n\}$.
  \begin{framed}
\vspace{-5mm}
\begin{small}
\begin{tabbing}
{\bf Algorithm} {\sf CountMinTransversals}$(\mathcal{H})$\\
\ \ \ \ \ \ \ $\mathcal{H}$: a $\beta$-acyclic hypergraph\\
1. Let $x_1,\ldots,x_n$ a $\beta$-elimination ordering of $\mathcal{H}$.\\
2. Let $e_1,\ldots,x_m$ the induced lexicographic ordering on $\mathcal{H}$.\\
3. Precompute $\mathcal{H}_{e_j}^{x_i},[\leq x_i]$ for every $i \leq n,j \leq m$. \\
4. {\bf for} $1\leq i\leq n$ and $i<\ell \leq n$ {\bf do}\\
5. \ \ \ {\bf for} $1\leq j \leq m$ {\bf do}\\
6. \ \ \ \ \ \ Compute $tab[i,j,0]$ from the recursive formula of $\#\mathsf{btr}_\emptyset(\mathcal{H}_{e_j}^{x_i},[\leq x_i])$.\\
7. \ \ \ \ \ \ Compute $tab[i,j,\ell]$ from the recursive formula of $\#\mathsf{btr}_{x_\ell}(\mathcal{H}_{e_j}^{x_i},[\leq x_i])$.\\
8. \ \ \ {\bf end for}\\
9. {\bf end for}\\
10. {\bf return} $tab[n,m,0]$
\end{tabbing}
\end{small}
\vspace{-5mm}
\end{framed}

In order to ease the presentation, the computation of $\#\mathsf{btr}_\emptyset(\mathcal{H}_e^x,[\leq x])$ and that of $\#\mathsf{btr}_w(\mathcal{H}_e^x,[\leq x])$ are separated, even though many of the arguments are similar.

\subsubsection{Base cases.} \label{subsubsec:base} We observe that for every $e \in \mathcal{H}$, $\mathcal{H}_e^{x_1}[\leq x_1]$ is either equal to $\{x_1\}$ or $\{\emptyset\}$. Thus, for every $e \in \mathcal{H}$ and $w \in V(\mathcal{H})$ such that $w > x_1$, we can compute $\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x},[\leq x_1])$ and $\#\mathsf{btr}_{w}(\mathcal{H}_e^{x},[\leq x_1])$ in time $O(1)$.

\subsubsection{Computing $\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x},[\leq x])$ by dynamic programming.} \label{subsubsec:empty}

We start by explaining how we can compute $\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x},[\leq
x])$ in polynomial time if the values $\#\mathsf{btr}_\emptyset(\mathcal{H}_f^{y},[\leq y])$ and $\#\mathsf{btr}_w(\mathcal{H}_f^{y},[\leq y])$ have been precomputed for $f \leq_\mathcal{H} e$ and $y < x$, $y<w$.

We start by applying Theorem~\ref{thm:inductivestep}.
\[
\begin{aligned}
\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x},[\leq x]) & =  \#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x}, [< x])  \\
& + \#\mathsf{btr}_{\emptyset}(\mathcal{H}_e^{x} \setminus \mathcal{H}_e^{x}(x) , [< x] )  \\
& - \#\mathsf{btr}_{x}(\mathcal{H}_e^{x}, [< x]).
\end{aligned}
\]

Now, let $C_1, \ldots, C_k$ be the connected components of $\mathcal{H}_e^{x}[< x]$. If there exists $i$ such that $C_i=\{\emptyset\}$, then
$\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x}, [< x]) = \#\mathsf{btr}_{x}(\mathcal{H}_e^{x}, [< x]) = 0$.  Otherwise, by applying Lemma~\ref{lem:betadecompo} with $S=\emptyset$, there exists, for
each $1\leq i \leq k$, $y_i < x$ and $f_i \leq_\mathcal{H} e$ such that $\mathcal{H}_{f_i}^{y_i}=\{g\in \mathcal{H}_e^f \mid g\cap [<x] \in C_i\}$ and $C_i = \mathcal{H}_{f_i}^{y_i}[\leq
y_i]$. By Lemma~\ref{lem:btrcc},
\begin{align*}
\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x}, [< x]) & = \prod_{i=1}^k \#\mathsf{btr}_{\emptyset}(\mathcal{H}_{f_i}^{y_i} , [\leq y_i]),\\
\#\mathsf{btr}_{x}(\mathcal{H}_e^{x}, [< x])  = &
\prod_{i=1}^k \#\mathsf{btr}_{x}(\mathcal{H}_{f_i}^{y_i} , [\leq y_i]) .
\end{align*}

We now show how to decompose $\#\mathsf{btr}_{\emptyset}(\mathcal{H}_e^{x} \setminus \mathcal{H}_e^{x}(x) , [< x] )$ into a product of precomputed values. Let $D_1,\ldots,D_l$ be the
connected components of $\mathcal{H}_e^{x} \setminus \mathcal{H}_e^{x}(x)[<x]$. If there exists $i$ such that $D_i=\{\emptyset\}$, then
$\#\mathsf{btr}_{x}(\mathcal{H}_e^{x} \setminus \mathcal{H}_e^{x}(x), [< x]) =0$.  Otherwise, if we apply Lemma~\ref{lem:betadecompo} with $S = \{x\}$, then there exists, for each
$1\leq i \leq l$, $y_i < x$ and $f_i \leq_\mathcal{H} e$ such that $\mathcal{H}_{y_i}^{f_i}= \{g\in \mathcal{H}_e^{x} \setminus \mathcal{H}_e^{x}(x) \mid g\cap [<x] \in D_i \}$ and
$D_i = \mathcal{H}_{y_i}^{f_i}[\leq y_i]$. We can thus conclude by Lemma~\ref{lem:btrcc} that
\[ \#\mathsf{btr}_{\emptyset}(\mathcal{H}_e^{x} \setminus \mathcal{H}_e^{x}(x) , [< x] ) = \prod_{i=1}^l \#\mathsf{btr}_{\emptyset}(\mathcal{H}_{f_i}^{y_i} , [\leq y_i]).\]

Therefore, if $\#\mathsf{btr}_{\emptyset}(\mathcal{H}_{f}^{y} , [\leq y])$ and $\#\mathsf{btr}_{x}(\mathcal{H}_{f}^{y} , [\leq y])$ have already been computed for every $f <_\mathcal{H} e$ and $y \leq x$,
we can compute $\#\mathsf{btr}_\emptyset(\mathcal{H}_e^{x},[\leq x])$ with at most $3 \times |\mathcal{H}_e^x|$ additional multiplications and $3$ additions.

\subsubsection{Computing $\#\mathsf{btr}_w(\mathcal{H}_e^{x},[\leq x])$ by dynamic programming.}\label{subsubsec:block} Let $x \leq w$. By Theorem~\ref{thm:inductivestep}, we have:
\[
\begin{aligned}
\#\mathsf{btr}_w(\mathcal{H}_e^{x},[\leq x]) & = \#\mathsf{btr}_{w}(\mathcal{H}_e^{x},[< x])  \\
& + \#\mathsf{btr}_{w}(\mathcal{H}_e^{x}\setminus \mathcal{H}_e^x(x),[< x])  \\
& - \#\mathsf{btr}_{\{x,w\}}(\mathcal{H}_e^{x}\setminus (\mathcal{H}_e^x(x) \cap \mathcal{H}_e^x(w)), [< x] ).
\end{aligned}
\]

We start by explaining how to compute $\#\mathsf{btr}_{w}(\mathcal{H}_e^{x},[< x]) $. Let $C_1,\dots,C_k$ be the connected components of $\mathcal{H}_e^x[<x]$. If there exists $i$ such that
$C_i=\{\emptyset\}$, then $\#\mathsf{btr}_{w}(\mathcal{H}_e^{x},[< x])=0$.  Otherwise, by Lemma~\ref{lem:betadecompo} with $S=\{w\}$, there exists, for each $1\leq i\leq k$,
$f_i \leq_\mathcal{H} e$ and $y_i < x$ such that $\mathcal{H}_{f_i}^{y_i}= \{g\in \mathcal{H}_e^{x} \mid g\cap [<x]\in C_i \}$ and $C_i = \mathcal{H}_{f_i}^{y_i}[\leq y_i]$. By
Lemma~\ref{lem:btrcc}, we can conclude that
\[ \#\mathsf{btr}_{w}(\mathcal{H}_e^{x},[< x]) =
\prod_{i=1}^k \#\mathsf{btr}_{w}(\mathcal{H}_{f_i}^{y_i}, [\leq y_i]). \]

We now explain how to compute $ \#\mathsf{btr}_{w}(\mathcal{H}_e^{x}\setminus \mathcal{H}_e^x(x),[< x])$. Let $D_1,\dots,D_l$ be the connected components of $(\mathcal{H}_e^{x}\setminus \mathcal{H}_e^x(x))[<x]$.
If there exists $i$ such that $D_i=\{\emptyset\}$, then $\#\mathsf{btr}_{w}(\mathcal{H}_e^{x}\setminus \mathcal{H}_e^x(x),[< x]) = 0$.
Otherwise, by applying Lemma~\ref{lem:betadecompo} with $S = \{x\}$, it follows that for every $1\leq i\leq l$, there exists $y_i < x$ and $f_i \leq_\mathcal{H} e$ such that $\mathcal{H}_{f_i}^{y_i} = \{g\in \mathcal{H}_e^{x}\setminus \mathcal{H}_e^x(x) \mid g\cap [<x]\in D_i \}$ and $D_i = \mathcal{H}_{f_i}^{y_i}[\leq y_i]$.
Thus, from  Lemma~\ref{lem:btrcc},
\[  \#\mathsf{btr}_{w}(\mathcal{H}_e^{x}\setminus \mathcal{H}_e^x(x),[< x])  =
\prod_{i=1}^l \#\mathsf{btr}_{w}(\mathcal{H}_{f_i}^{y_i}, [\leq y_i]).\]

Finally, we explain how to decompose $\#\mathsf{btr}_{\{x,w\}}(\mathcal{H}_e^{x}\setminus (\mathcal{H}_e^x(x) \cap \mathcal{H}_e^x(w)), [< x] )$ into a product of pre-computed values. To ease the
notation, we denote $\mathcal{H}_e^{x}\setminus (\mathcal{H}_e^x(x) \cap \mathcal{H}_e^x(w))$ by $\mathcal{H}'$.  Let $K_1,\dots,K_r$ be the connected components of $\mathcal{H}'[<x]$. If there exists
$i$ such that $K_i=\{\emptyset \}$, then $\#\mathsf{btr}_{\{x,w\}}(\mathcal{H}', [< x] )=0$.  Otherwise, by Lemma~\ref{lem:betadecompo} applied with $S = \{x,w\}$, we have that for every
$i$, there exists $y_i < x$ and $f_i \leq_\mathcal{H} e$ such that $\mathcal{H}_{f_i}^{y_i}= \{g\in \mathcal{H}' \mid g\cap [<x] \in K_i \}$ and $K_i = \mathcal{H}_{f_i}^{y_i}[\leq y_i]$. By
Lemma~\ref{lem:btrcc}, we have:
\[ \#\mathsf{btr}_{\{x,w\}}(\mathcal{H}_e^{x}\setminus (\mathcal{H}_e^x(x) \cap \mathcal{H}_e^x(w)), [< x] ) =
 \prod_{i=1}^r \#\mathsf{btr}_{\{x,w\}\cap V(\mathcal{H}_{f_i}^{y_i})}(\mathcal{H}_{f_i}^{y_i},[\leq y_i]). \]

\begin{claim}
\label{clm:bcapci3}
  For every $i \leq p$, $ \{x,w\}\cap V(\mathcal{H}_{f_i}^{y_i})\neq \{x,w\}$.
\end{claim}
\begin{proof}
Assume towards a contradiction that $\{x,w\}\cap V(\mathcal{H}_{f_i}^{y_i})= \{x,w\}$. Recall that $\mathcal{H}_{f_i}^{y_i}[\leq y_i]$. By Lemma \ref{lem:hexvar}, $\{x,w\}\subseteq V(\mathcal{H}_{f_i}^{y_i})$ implies $\{x,w\}\subseteq f$. Thus, we have $f\in \mathcal{H}_e^x(x)\cap\mathcal{H}_e^x(w)$. This is a contradiction, since $f\in \mathcal{H}_{f_i}^{y_i} \subseteq \mathcal{H}_e^x \setminus (\mathcal{H}_e^x(w) \cap \mathcal{H}_e^x(x)) $.
\end{proof}

Thus, $\{x,w\}\cap V(\mathcal{H}_{f_i}^{y_i})$ equals either $\{x\}$, or $\{w\}$ or $\emptyset$ by Claim \ref{clm:bcapci3}. That is, we can compute
$\#\mathsf{btr}_{\{x,w\}}(\mathcal{H}_e^{x}\setminus (\mathcal{H}_e^x(x) \cap \mathcal{H}_e^x(w)), [< x] )$ from precomputed terms.

We can conclude that, if $\#\mathsf{btr}_{\emptyset}(\mathcal{H}_{f}^{y} , [\leq y])$ and $\#\mathsf{btr}_w(\mathcal{H}_{f}^{y} , [\leq y])$ have already been computed for every $f <_\mathcal{H} e$ and
$y \leq w$, we can compute $\#\mathsf{btr}_w(\mathcal{H}_e^{x},[\leq x])$ with at most $3 \times |\mathcal{H}_e^x|$ additional multiplications and $3$ additions.

\medskip

It is easy to see that a straightforward greedy algorithm can be used to compute a $\beta$-elimination ordering in polynomial time (see \cite{PaigeT87} for a better
algorithm due to Paige and Tarjan). Moreover, the dynamic programming algorithm describes above computes at most $O(n^2|\mathcal{H}|)$ terms and each of them can be computed
from the others with a polynomial number of arithmetic operations. Finally, all these terms can be bounded by $2^n$ since they are all the cardinals of some collection of
subsets of the vertices. Thus these arithmetic operations can be done in polynomial time in the size of the input. It follows.

\begin{theorem}[Main Theorem]\label{thm:main}
  Let $\mathcal{H}$ be a $\beta$-acyclic hypergraph. One can compute in polynomial time the number of minimal transversals of $\mathcal{H}$.
\end{theorem}

\section{Applications to the counting of Dominating Sets}
\label{sec:dom}

We refer to \cite{Diestel05} for our graph terminology. For a graph $G$, let $V(G)$ be its set of vertices and $E(G)$ be its set of edges. For a vertex $x$ of a graph
$G$, let $N(x)$ be the set of neighbours of $x$ and we let $N[x]$ be the set $\{x\}\cup N(x)$. The \emph{closed neighbourhood hypergraph} of $G$, denoted by $\mathcal{N}[G]$, is
the hypergraph $\{N[x]\mid x\in V(G)\}$. A \emph{dominating set} in a graph $G$ is a transversal of $\mathcal{N}[G]$. \textsc{Dominating Set} problems are classic and
well-studied graph problems, and has applications in many areas such as networks and graph theory \cite{HaynesHS98}.

In \cite{KanteLMN14} the authors reduce the \textsc{Hypergraph Dualisation} problem into the enumeration of minimal dominating sets, showing that the two problems are equivalent in the area of enumeration problems
(a fact already established in the case of optimisation).  The reduction indeed shows that the counting versions are equivalent (under Turing reductions), and such a
reduction is of big interest because it allows to study counting and enumeration problems associated with the \textsc{Hypergraph Dualisation} in the perspectives of graph
theory, where tools had been developed to tackle combinatorial problems.

Despite the broad application of counting the minimal dominating sets in (hyper)graphs, the problem was not investigated until recently, except in \cite{Courcelle06}
where it is proved that the models of any monadic second-order formula can be counted in polynomial time in graphs of bounded clique-width.
Indeed, as far as we know the counting of minimal dominating sets is only considered in \cite{KanteLMNU13,GolovachHKKSV17,KanteU17}.
This problem is known to be polynomial on interval graphs and permutation graphs \cite{KanteLMNU13}.
However, the systematic study of its computational complexity in graph classes is only considered in \cite{KanteU17}, where the authors proved the $\#$P-completeness in several graph classes and asked whether the following dichotomy conjecture is true. A $k$-sun is a graph obtained from a cycle of length $2k$ ($k\geq 3$) by adding edges to make the even-indexed vertices pairwise adjacent. A graph is \emph{chordal} if it does not contain cycles of length at least $4$ as induced subgraphs.

\begin{conjecture}\label{conj:dichotomy-chordal}
  Let $\mathcal{C}$ be a class of chordal graphs. If $\mathcal{C}$ does not contain a $k$-sun as an induced subgraph, for $k\geq 4$, then one can count in polynomial time the number
  of minimal dominating sets of any graph in $\mathcal{C}$. Otherwise, the problem is $\#$P-complete.
\end{conjecture}

This conjecture is motivated by the recursive structure of the chordal graphs without $k$-sun, for $k\leq 4$.

We make a first step towards a proof of the first statement of the conjecture and provide a polynomial time algorithm for computing the minimal dominating sets in \emph{strongly chordal graphs}, which are exactly chordal graphs without $k$-suns, for $k\geq 3$.

\begin{corollary}[Main Corollary] Let $G$ be a strongly chordal graph. One can count in polynomial time the number of minimal dominating sets of $G$.
\end{corollary}

\begin{proof} Let $G$ be a strongly chordal graph. It is well-known that the hypergraph $\mathcal{N}[G]$ is $\beta$-acyclic
  \cite{BrandstadtLS99}. By Theorem \ref{thm:main}, one can count in polynomial time the minimal transversals of $\mathcal{N}[G]$, which are exactly the minimal dominating sets
  of $G$.
\end{proof}

\section{Conclusion}\label{sec:conclusion}

We proposed a polynomial time algorithm for counting the minimal transversals of any $\beta$-acyclic hypergraph, supporting Conjecture \ref{conj:dichotomy-chordal}, and it seems that the technique can be easily
adapted to consider (inclusion-wise) minimal $d$-dominating sets, which are dominating sets such that each vertex is dominated by at least $d$ vertices \cite{GolovachHKKSV17}.

Besides resolving Conjecture \ref{conj:dichotomy-chordal}, there are two immediate questions that deserve to be considered. Firstly, can we count the minimal models of
any non-monotone $\beta$-acyclic formula in polynomial time? Secondly, for which graph classes and counting graph problems the techniques of this paper apply?

\bibliographystyle{elsarticle-num}

redpajama_set_name: RedPajamaArXiv


text:
Microsoft Surface Go: Specs, price, features and release date
Mayank Parmar
Microsoft Surface Go is smallest, lightest, and most affordable Surface model ever released. It has made headlines lately as the company's "low-cost Surface". In this article, we will talk about Surface Go specs, price and the release date.
Microsoft Surface Go specifications
It features a 10-inch 3: 2 aspect 1800 x 1200 display with 216 PPI.
Supports up to 4,096 levels of pressure.
Powered by Intel Pentium Gold 4415Y clocked at 1.6GHz and Intel HD 615 is included for graphics.
Comes in 4GB of RAM and 8GB RAM options.
Available in three storage options – 64GB eMMC, 128GB and 256GB SSD.
It features a 5MP front-facing camera with Windows Hello, 8MP rear auto-focus rear camera, rounded corners and fanless design.
Ports: 1x USB-C 3.1, microSD (up to 1TB), Surface Connect, headphone jack.
Supports Dolby Audio Premium, Windows Hello and Surface Pen.
Connectivity: Wi-Fi 802.11 a/b/g/n/ac, Bluetooth 4.1.
It weighs 1.15 lbs (0.52 kg) without keyboard and 1.7lbs (0.77 kg) with keyboard.
Battery up to 9 hours.
Available in Magnesium colour.
Starts at $399 plus $99 for optional keyboard or $129 for an optional keyboard with Alcantara.
Microsoft Surface Go Price
The device will go on sale on August 2 and can be pre-ordered for $399. The new Type Covers will cost an extra $9.
Microsoft will also sell the special-edition Alcantara version of the keyboard which is priced at $129.
Microsoft Surface Go Release Date
The device will go on sale on August 2. It can be pre-ordered in the US, Canada, UK Australia, New Zealand, UK, Ireland, France, Germany, Austria, Belgium, Luxembourg, Netherlands, Switzerland, Denmark, Finland, Norway, Sweden, Poland, Italy, Portugal, and Spain.
It's coming to China, Japan, Singapore, Korea, Taiwan, Malaysia, Thailand and Hong Kong in a few weeks.
Microsoft Teams to get meeting recap support, new navigation experience
Chrome could soon run better on Windows, thanks to Microsoft
Microsoft's new Surface Pro 7+ comes with 4G LTE and 11th gen Intel
Microsoft Edge to get a new feature for managing downloads
Microsoft Surface Laptop 4 lineup could include more AMD options

redpajama_set_name: RedPajamaCommonCrawl


Nobody ever wants to see a gigantic moon dropping from the sky. In this video shared by NASA, special lens make the phenomenon look startlingly real.
Three cosmic events light up (or darken) the sky on the last day of the week.
NASA senior photographer and a UK astrophotographer shared tips on how to photograph the supermoon like a pro.
NASA says the supermoon this Nov. 14 will be the biggest this century.
A supermoon is a full moon that is closer to Earth than average. This November, the full moon or supermoon will be the biggest and brightest since 1948. Find out where, when and how to see November's supermoon.
A penumbral lunar eclipse and a full harvest moon will occur at the same time on Sept. 16 for the second year in a row.
To signal the end of summer and start of autumn this year, the Harvest Moon will rise this Sept. 16. The Harvest Moon is also dubbed as the Pumpkin Moon because of its color. Here are fast facts you should know about this rare occurence.
This month's full moon occurs on July 19 and it is one of the most popular full moon known as buck moon.


text:
What is an Arts School?
An arts school is a place that
Allows you to express your art, whatever it is (and teaches you how to do it better!)
Stresses Academics (college prep all the way!)
Teaches you to be a better artist, singer, instrumentalist, technician, scholar, musician, dancer, and person
Teaches you to appreciate the arts
Teaches you to appreciate others
Teaches you respect
Teaches you compassion
Holds you to a higher standard.
Allows you to shine in your own individual way.
Allows you to fit in (there is a place here for everyone)
Gives you a venue to perform
What we are not:
A place to stay in the shadows
A place to escape the pressure of accountability
A place to get by with studying a little (we are a college prep school!)
A place to not participate in the arts (after all, we are an art school!)
A place to sit back and watch the action (you will be expected to be in the middle of it)
A place to take the bare minimum of classes (we require more core classes than some other schools)
If you fit this criteria, please consider joining us. We know we are not for everyone, but we have something for almost everyone. We are not an easy school. Just try balancing your daily studies and your artistic endeavors at once!
We will teach you organizational skills and how to succeed in life. We don't just teach you to be artists; we teach you to be good citizens. We teach the appreciation of the arts. We teach people. We love what we do, and it shows.
Charter School FAQ
Charter schools are public schools that operate under a "charter," or "charter contract" which frees them from many regulations created for traditional public schools while holding them accountable for academic and financial results. The charter contract is between the charter school's sponsoring entity and the Arkansas State Board of Education or the Commissioner of Education.
"Charter," or "charter contract" means a performance-based contract for an initial five-year period between the authorizer and an approved applicant for public charter school status that exempts the public charter school from state and local rules, regulations, policies, and procedures specified in the contract and from the provisions of Title 6 of the Arkansas Code specified in the contract.
Source: Ark. Code Ann. § 6-23-103(2)
Why do parents choose charter schools?
Charter schools provide families a choice in the education of their children – and it is a public choice. Public tax dollars are the primary funding sources for charter schools. Local, state, and federal dollars follow the child to a charter school. The schools have open enrollment with no discrimination, no religious associations, and no tuition.
What is the legislative and regulatory intent behind charter schools?
It is the intent of the Arkansas General Assembly, and of these rules, to provide opportunities for teachers, parents, pupils, and community members to establish and maintain public schools that operate independently from the existing structure of local school districts as a method to accomplish the following:
Improve student learning;
Increase learning opportunities for all students, with special emphasis on expanding learning experiences for students who are identified as low-achieving;
Encourage the use of different and innovative teaching methods;
Create new professional opportunities for teachers, including the opportunity to be responsible for the learning program at the school site;
Provide parents and pupils with expanded choices in the types of educational opportunities that are available within the public school system; and
Hold the schools established under this chapter accountable for meeting measurable student achievement standards.
Source: Ark. Code Ann. § 6-23-201
Who can start and open-enrollment charter school?
The following are considered eligible entities and may apply to the State Board of Education to create an open-enrollment charter school:
A public institution of higher education;
A private nonsectarian institution of higher education;
A governmental entity; or
An organization that is nonsectarian in its program, admissions policies, employment practices, and operations, and has applied for tax-exempt status under § 501(c)(3) of the Internal Revenue Code of 1986. The eligible entity must obtain status as a tax-exempt organization under § 501 (c)(3) of the Internal Revenue Code of 1986 prior to the first day of its operation with students.
What is the application process for establishing charter schools?
Although the annual timelines are different, the charter application process is very similar for both open-enrollment and district conversion charter applicants and includes the following steps:
The State Board of Education (SBE) approves the document to be used as an application
Potential applicants submit letters of intent to apply for charters to staff at the Arkansas Department of Education (ADE)
ADE staff conducts a technical assistance conference
Applicants submit their applications
Applications are reviewed and evaluated, based on a rubric published as part of the application packet, by staff from various divisions at the ADE
Applicants receive evaluations with comments from ADE staff
Applicants respond to the comments and submit the responses
ADE staff who reviewed and evaluated the original applications review responses and reevaluate
The Charter Authorizing Panel interviews applicants and takes action on the applications in a public meeting
Do charter schools have admission policies?
Families must contact each individual charter school to see if they have openings. If they have more applicants than available slots, an open lottery must be instituted to fill the remaining slots and create a waiting list.
How are open-enrollment charter schools funded?
An open-enrollment public charter school shall receive funds equal to the amount that a public school would receive under § 6-20-2305(a) and (b) as well as any other funding that a public charter school is entitled to receive under law or under rules promulgated by the State Board of Education.
Source: Arkansas Charter Schools Act of 1999, Chapter 23, subchapter 5
See also: http://www.arkansased.gov/divisions/legal/legal-links–Arkansas Code


They do in fact investigate them.
If an accident or serious incident occurs in a foreign state involving a civil aircraft of U.S. Registry, a U.S. operator, or an aircraft of U.S. design or U.S. manufacture, where the foreign state is a signator to the ICAO Convention, that state is responsible for the investigation. In accord with the ICAO Annex 13 SARPS, upon receipt of a formal notification of the accident or serious incident that may involve significant issues, the NTSB may designate a U.S. Accredited Representative and appoint advisors to carry out the Obligations, receive the Entitlements, provide Consultation, and receive Safety Recommendations from the state of occurrence.
If an accident or serious incident occurs in a foreign state not bound by the provisions of Annex 13 to the ICAO Convention, or if a foreign state delegates all or part of an investigation by mutual consent to the NTSB, or if the accident or serious incident involves a public aircraft, the conduct of the investigation shall be in consonance with any agreement entered into between and the United States and the foreign state.
Last Sunday booked flights for us, Melb. to Cebu via Singapore on May8.
Had a look at the ticket and we are supposed to be on the Silk-Air Boing 737 from Singas to Cebu.
Hope they have changed the spark plugs and tuned the carby before then!
Could be April Fools Day?
and likely ticket prices will jump.
Shortly after posting the above I checked prices and found a BClass ticket CEB-ORD in Sep returning Oct for under $1K on China Eastern, the next day over $2k for the same. Now, can't find it at all.
The unheard of 1K is the best price I have ever seen for a Bclass from cebu to ord...Even 2k is outstanding...The best I ever got was $2500 with China Eastern..But I hated that 5am departure and the TSA witches in Shanghai were some of the least friendliest looking people I have met..I will gladly pay in the $3000 range for Korean Air..Just my personal opinion..
We did BClass same route under $1500 last year may-jun but told the wife not to get used to it. Over $1500 would be out of my range. I'd rather spend the extra on the trip itself. Some time after the Max planes are repaired, there will likely be a big drop.
I was just looking on the CE site. ph.ceair.com or something like that. When I looked before early sep to mid oct I had under $1k. The next day over $2k. Now I get nothing in any class. I think CE has about 25 Maxs. But it doesn't matter, even if the route you take isn't on a Max or even if your favorite airline doesn't use them, tickets are going fast because of this.
The 737 MAX has its engines placed much higher than other commercial jets have. There were some newer, more economical engines that Airbus was already using, and Boeing did not want to lose business, but they had a problem: The 737 wings were closer to the ground than its nearest Boeing rival's were, and so it could not mount the engines in the same way. So they put the engines on pylons pushing them in front of the wing, with the tops of the engines poking out ABOVE the wing. This tended to produce an accelerated angle of attack, so they installed MCAS----which was supposed to push the nose down automatically to avoid a stall. Boeing barely offered any training in respect of the new system. They were in quite a hurry to compete with Airbus. Now it is too late for them to be careful. Boeing will likely have a lot of paying out to do in court, and even more with lost orders. How many airlines are now experiencing buyer regret for having gone with Boeing on the 737 MAX? This blunder might decide the Boeing versus Airbus rivalry.
Too many variables, unpredictable events and " hackers".
As long as the automation does better than the meat alternative, it's irrelevant from a rational standpoint. Perfection is an impossible bar to clear.
I have found some oddities over the years with fares, at times the travel agents beat internet prices among others.
I am not under any time constrains when I travel can go and return when I feel like it and have lots of time to shop price on the net.
So if I am looking and prices are running say $1200 to $1500 US and a fare shows up for $920, I double check the connections, need to make sure there is not a 19 hour layover at JFK or need to change airports Newark to JFK or some such thing. I do not leave the page I do not pass go, I do not hesitate but buy the ticket on the spot. I know from past experience it will not be there even 2 hours later.
No idea why this is, only that on occasion a low fare will show up and then disappear.


text:
Does ETF Pay Dividends Singapore?
Dividends on exchange-traded funds (ETFs). Qualified and non-qualified dividends are the two types of dividends paid to ETF participants. If you own shares of an exchange-traded fund (ETF), you may get dividends as a payout. Depending on the ETF, these may be paid monthly or at a different interval.
What are the signs that an ETF pays dividends?
An ETF, like a stock, has an ex-dividend date, a record date, and a payment date, just like a company's stock. These dates define who is eligible to receive the dividend and when it is paid. The dividend payments are made on a different timetable than the underlying stocks, and the timing varies based on the ETF.
The ex-dividend date for the popular SPDR S&P 500 ETF (SPY), for example, is the third Friday of the fiscal quarter's last month (March, June, September, and December). If that day isn't a business day, the ex-dividend date will be the previous business day. The ex-dividend date is two days before the record date. The dividends are distributed by the SPDR S&P 500 ETF at the end of each quarter.
Do dividend ETFs pay out every month?
Dividend-paying exchange-traded funds (ETFs) are becoming increasingly popular, particularly among investors seeking high yields and greater portfolio stability. Most ETFs, like stocks and many mutual funds, pay dividends quarterly—every three months. There are, however, ETFs that promise monthly dividend yields.
Monthly dividends can make managing financial flows and budgeting easier by providing a predictable income source. Furthermore, if the monthly dividends are reinvested, these products provide higher overall returns.
Are dividend-paying ETFs better?
Dividend ETFs Have a Lot of Advantages. ETFs that pay dividends have a variety of appealing features. Dividend ETFs, in particular, may save investors a lot of time and potential difficulties when compared to holding individual companies, in my opinion.
How are dividends from REIT ETFs taxed?
How are dividends from REIT ETFs taxed? After the 20% qualifying business income deduction is applied to those distributions, most REIT ETF dividends will be taxed at your regular income tax rate. Some REIT ETF earnings may be subject to capital gains tax, which will be reported on Form 1099-DIV.
How do dividends in ETFs work?
ETFs (exchange-traded funds) pay out the entire dividend from the equities owned within the fund. Most ETFs do this by keeping all of the dividends received by underlying equities during the quarter and then paying them out pro-rata to shareholders.
Which REITs pay dividends every month?
REITs (real estate investment trusts) are an excellent way to earn consistent income.
Only a few REITs pay dividends on a regular basis, such as monthly or quarterly.
AGNC Investment Corp. (AGNC) and STAG Industrial are two of the most well-known monthly dividend payers (STAG).
Other monthly dividend REITs, such as Apple Hospitality (APLE) and Bluerock Residential Growth (BRG), have stopped paying dividends or have ceased them entirely (BRG).
Are REIT dividends tax deductible?
The majority of REIT distributions are classified as non-qualified dividends, meaning they are not eligible for the capital gains tax rate. In most circumstances, qualifying dividends are taxed at a 15% capital gains rate, whereas non-qualified dividends are taxed at the individual's regular income tax rate.
What Is IWDA ETF?
What Is Mutual Fund vs ETF?
What Is IWM ETF?
What Is My Verizon ETF?
What Is JNK ETF?
What Is NASDAQ 100 ETF?


text:
Raad van Politie (Aruba), voormalige wetgevende macht in Aruba
 Raad van Politie (Guyana), voormalige wetgevende macht in Nederlands-Guiana en Brits-Guiana
 Raad van Politie (Suriname), voormalige rechterlijke macht in de kolonie Suriname

redpajama_set_name: RedPajamaWikipedia


text:
This Day in History: John F. Kennedy & PT-109
On this day in 1943, surviving crew members of PT-109 are finally rescued. That small boat had been under the command of Lt. (j.g.) John F. Kennedy when it was rammed by a Japanese destroyer.
Kennedy would come home a war hero, but the incident has not been without controversy. Did Kennedy's decisions put PT-109 in danger? Was he a hero or should he have been court-martialed? What about other heroes aboard the vessel? Why have they been forgotten?
John F. Kennedy with some of his crew
On the night of August 1-2, Kennedy's boat was one of 15 PTs sent to patrol the Blackett Strait in the Solomon Islands. They were looking for the "Tokyo Express," a Japanese supply convoy that ran through the area.
The mission was going badly. PTs fired upon the Japanese destroyers, but to no avail. Some PTs ran out of torpedoes and left. Kennedy's boat was among those that remained behind.
They were waiting for the Japanese convoy to return, then they would try again.
Understanding what followed, a JFK library archivist writes, requires remembering "that it was dark—deeply, unrelievedly dark. . . . [The disorienting effect] of a moonless, starless night on the ocean should not be underestimated."
At about 2:30 a.m., the Japanese destroyer Amagiri arrived.
"Suddenly a dark shape loomed upon PT 109's starboard bow 200-300 yards distant," a Navy report noted. "At first this shape was believed to be other PTs. However, it was soon seen to be a destroyer . . . . The 109 started to turn to starboard preparatory to firing torpedoes. However, when PT 109 had scarcely turned 30 degrees, the destroyer rammed the PT . . . ."
Was Kennedy at fault? He had only one engine running when Amagiri appeared. Kennedy was trying to avoid detection, but his decision made it hard to move quickly. On the other hand, the overall mission had been plagued by problems beyond Kennedy's control. For instance, why were all the radar-equipped PTs ordered to leave so early? It handicapped those left behind.
The problems were so bad that one account calls the mission the "most confused and least effective action the PTs had been in." Either way, no one disputes what came next.
Amagiri plowed into PT-109, cutting it in half. Fuel spilled out—and exploded. Two men were lost instantly. Eleven others survived, clinging to what remained of PT-109 as she slowly sank. Some of these men survived only because Kennedy swam out into the ocean to retrieve them. Twelve hours later, the men were finally forced to abandon ship. They'd have to swim to a small island several miles away.
One of the men—boat engineer "Pappy" McMahon—had serious burns. He lay on Kennedy's back as Kennedy towed them both to the island, holding the strap of McMahon's life jacket between his teeth.
Five hours later, the survivors finally reached a tiny, uninhabited island.
Kennedy had to have been exhausted. He'd accomplished all this, despite injuring his back during the initial collision. Yet he refused to rest. The little island was close to a passage used by other PT boats. Kennedy swam out in an (ultimately futile) attempt to flag down a friendly ship.
The ordeal was just beginning. In the days that followed, the survivors would relocate to another island, looking for food. Kennedy swam for help multiple times, as did another crew member. Fortunately, island scouts for the Allies would eventually find the survivors. Kennedy famously scratched out a message on a coconut shell, and the scouts took it to the Americans.
"NAURO ISL…COMMANDER…NATIVE KNOWS POS'IT…HE CAN PILOT…11 ALIVE…NEED SMALL BOAT…KENNEDY."
It was the beginning of the end of the ordeal. On August 8, the men were finally rescued.
Edward J. Renehan, Jr., The Kennedys at War: 1937-1945 (2002)
John F. Kennedy and PT 109 (JFK Library website)
Owen Edwards, Remembering PT-109 (Smithsonian Magazine; Summer 2010) (reprinted HERE)
Robert Dallek, An Unfinished Life: John F. Kennedy, 1917 – 1963 (2004)
Stephen Plotkin, Sixty Years Later, the Story of PT-109 Still Captivates (Prologue Magazine; Summer 2003) (reprinted HERE)


text:
        <button id="dLabel" class="btn btn-primary btn-sm" type="button" data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
            ETL操作
        </button>

ETL属性

规则配置

表过滤

操作过滤

已配置规则

批量配置

批量配置值绑定

<ui-view></ui-view>

redpajama_set_name: RedPajamaGithub


Bitcoin has a bit of James Bond flair to it. Encryption, secret keys, anonymity and the ability to send money around the world instantly as part of a growing shadow economy is all good fun.
Detail of the encrypted key as graphed by the AndroSpectro app.
But Sound Wallet takes this latent spy esthetic to a delightfully extreme new level by taking a BIP38 encrypted key and converting it into a sound file which, to the casual listener, will just sound like static. Listen to that sound with an app called AndroSpectro (or Audacity with the right settings), though, and out of the static emerge the characters that comprise the encrypted key.
But that wasn't extreme enough for bitcointalk user krach. Sure, you can have him email you the .wav file, or burn it onto a CD, but you can also have him cut it into a 7″ vinyl record.
And that is unbelievably groovy.
A picture of the shape of the sound of Bitcoin.
The burst of gentle static at the beginning of the record contains the key, but then the recording transitions smoothly into some harsh electronic music. This is a great touch, as anyone snooping through your record collection will think it's just an obscure recording.
This is such a fun object. It would be a great way to hide a key in plain sight, certainly, but it's also such an elaborately conceived and constructed wallet that it feels like a piece of art.


PEORIA--Velda I. Edenburn, 91, of Peoria, passed away at 1:40 a.m. Saturday, March 16, 2019 at UnityPoint Health - Methodist.
Born July 6, 1927 in Bartonville, a daughter of Walter and Ada Gann Moore, Velda married Lyle M. Edenburn September 8, 1946 in Peoria. He preceded her in death.
Also preceding her in death were four brothers.
She is survived by one sister, Lela Josephson of Peoria.
Velda enjoyed working with needlepoint.
She was a member of Grace and Peace Lutheran Church where funeral services will be at 10 a.m. Thursday, March 21, 2019. Reverend Mary Benken will officiate. Visitation will be from 9:30 a.m. to 10 a.m. Thursday at the church. Burial will be in Swan Lake Memory Gardens.
"Email Address" would like to share the life celebration of Velda I. Edenburn. Click on the "link" to go to share a favorite memory or leave a condolence message for the family.


ARPEL Magazine Companies ABC Morini s.r.l.
ABC MORINI, established in 1969, it's a leader company in the creation of accessories for the italian and international leather goods industry.
A company that for over forty years has characterized, with its footwear accessories, handbag accessories and belts accessories, the most exclusive and charming leather goods.
Unique and functional designes and a continuous creative research based on the values of elegance, balance, beauty and volumetric ratio are the main strenghts of this company.
ABC Morini is a serious and reliable company, able to offer guarantee the customers a tailor made and concrete service thanks to a high-qualified team of passionate workers and designers able to read the new market's needs with contemporary, stylish taste.
Latest photos for ABC Morini s.r.l.
All the news about ABC Morini s.r.l.
See some products from ABC Morini s.r.l.


text:
"""
tworld: Copyright (c) 2013, Andrew Plotkin
(Available under the MIT License; see LICENSE file.)

This is the top-level script which acts as Tworld's core server.

Players do not connect directly to this process. The tweb server (the web
server process) connects to this; players connect to tweb. All game
commands are relayed to us through tweb.
"""

import sys
import types
import logging

import tornado.options
import tornado.ioloop
import tornado.autoreload

# Set up all the options. (Generally found in the config file.)

# Clever hack to parse a config file off the command line.
tornado.options.define(
    'config', type=str,
    help='configuration file',
    callback=lambda path: tornado.options.parse_config_file(path, final=False))

tornado.options.define(
    'python_path', type=str,
    help='Python modules directory (optional)')

tornado.options.define(
    'debug', type=bool,
    help='application debugging (see Tornado docs)')
tornado.options.define(
    'show_stack_traces', type=bool,
    help='show stack traces for errors that are probably a player\'s fault')
tornado.options.define(
    'log_level', type=str, default=None,
    help='logging threshold (default usually WARNING)')
tornado.options.define(
    'log_file_tworld', type=str, default=None,
    help='log file to write to (default is stdout)')

tornado.options.define(
    'tworld_port', type=int, default=4001,
    help='port number for communication between tweb and tworld')

tornado.options.define(
    'mongo_database', type=str, default='tworld',
    help='name of mongodb database')

# Parse 'em up.
tornado.options.parse_command_line()
opts = tornado.options.options

if opts.python_path:
    sys.path.insert(0, opts.python_path)

# Set up the logging configuration.
logconf = {
    'format': '[%(levelname).1s %(asctime)s: %(module)s:%(lineno)d] %(message)s',
    'datefmt': '%b-%d %H:%M:%S',
    }
if opts.log_level:
    logconf['level'] = opts.log_level
if opts.log_file_tworld:
    logconf['filename'] = opts.log_file_tworld
else:
    logconf['stream'] = sys.stdout
logging.basicConfig(**logconf)

# Now that we have a python_path, we can import the tworld-specific modules.

import twcommon.autoreload
import two.app
app = two.app.Tworld(opts)

if opts.debug:
    twcommon.autoreload.sethandler(app.autoreload_handler)
    tornado.autoreload.start()

tornado.ioloop.IOLoop.instance().start()


text:
The keynote session on Day 3 focused on "Current Trends in Fundraising."
By Gabby Houck and Jessie Farrigan
As fundraisers find themselves emerging from two challenging years and preparing for the possible recession in the year ahead, Bill Stanczykiewicz — senior assistant dean for external relations, clinical associate professor, director of The Fund Raising School and Rosso Fellow at Indiana University's Lilly Family School of Philanthropy — is focusing on trends impacting giving specifically in times of economic downturn.
On the final day of the NonProfit POWER conference, Stanczykiewicz opened the final day of the event with his keynote, "Current Trends in Fundraising." His takeaways were surprising.
Charitable Giving During Recessions
To kick off the final day of the event, Bill Stanczykiewicz, senior assistant dean for External Relations, Clinical Associate Professor, Director of The Fund Raising School and Rosso Fellow at Indiana University's Lilly Family School of Philanthropy, took the stage for a keynote session.
Fundraisers can rest assured knowing that recessions and economic downturns are normal and that a proper planning strategy can be implemented to handle these events. Despite common misconceptions about charitable giving in times of economic recessions, statistics from the Lilly Family School of Philanthropy depict that the average increase in charitable giving goes up 3.3% after inflation. The average decrease in charitable giving in recession years only goes down 0.5%.
Stanczykiewicz presented this trend with the silver lining that while giving is, of course, impacted by inflation, it never goes away completely and often bounces back positively.
"Just as there is a desire to get back to spending, there is a desire to get back to typical charitable giving behavior once we've weathered the recession," he said.
Fundraising Strategies in Economic Downturns
For fundraisers tasked with carving out the path for giving during economic downturns, Stanczykiewicz recommended turning to crisis leadership. Crisis leadership calls for scenario planning, making decisions that are not irreversible, analyzing events and trends in a manner that is not black and white, and inviting expertise from various sources. In other words, fundraisers should do the best they can with the information that they have.
However, strategic planning should exist beyond the window of recessions, so that organizations can be prepared beforehand. Strategies may include annual budgeting that builds an operating reserve, identifying new donors before a recession starts, empathy for donors regarding financial challenges, including the negative effects of a recession in your fundraising case for support, and continued stewardship of current donors.
It's important to remember that while every gift matters, current donors will be more willing to give if stewardship is valued and practiced within your nonprofit.
"Fundraising happens at the speed of trust," Stanczykiewicz said. "Donors love stability, and if they have to choose and limit, they're going to choose the nonprofit with which they have the closest relationship."
As the year ahead remains unpredictable, it's up to fundraisers to seek out every possible opportunity to meet donors where they are and maintain stewardship. While dips in charitable giving may occur in correlation to difficult economic times, strategic planning will ensure that nonprofit organizations will be able to weather the storm when giving most definitely rebounds.
The Importance of Community
From left, Logan Echard, the director of analytics and strategy at Four Diamonds, and Katrina VanHuss, founder and CEO of Turnkey, took the stage for the final educational session of the NonProfit POWER event.
Following the keynote session, Logan Echard, the director of analytics and strategy at Four Diamonds, and Katrina VanHuss, founder and CEO of Turnkey took the stage to talk about the identities of those who support a nonprofit's cause, and the community that can form from those supporters.
VanHuss urged the audience to move away from the notion of the email list, and instead give donors and volunteers a way to communicate with one another to form a sense of community.
"We describe our community often in nonprofit as our constituents, and by that, we mean the people on our email list, but our email list is not a community," VanHuss said. "We have not provided them a way to talk to each other; we've provided a way for us to talk to them. We've sometimes provided a way for them to talk to us. We've provided them to talk to the outside world peer to peer. But what we haven't built is a way for them to talk to each other."
In order to build a community, VanHuss and Echard used THON – which Echard works very closely with – as an example.
"You volunteer to be part of our nation, but you don't register, that language isn't even used, you're joining a community, that's what you're becoming part of," VanHuss said.
For more information from the event, check out our coverage from Day 1 here and Day 2 here.
Save the Date for NonProfit POWER 2023
Next year's NonProfit POWER will take place at the Hilton Inner Harbor in Baltimore from Dec. 4-6, 2023. Stay informed on when more details are available for the next NonProfit POWER by subscribing to NonProfit PRO's e-newsletter or checking the NonProfit POWER event site.
E Gabby Houck Author's page
E Jessie Farrigan Author's page
Jessie Farrigan is the online and production editor for the Printing & Packaging Group at NAPCO Media.
Trends in Impact Evaluation That Can Work in Your Favor


Image Title: Red And Black King Size Comforter Sets ChoozOne Inside Set Prepare 4. Filename: red-and-black-king-size-comforter-sets-choozone-inside-set-prepare-4.jpg. Image Dimension: 620 x 453 pixels. Images Format: jpg/jpeg. Publisher/Author: Domenic Goodwin. Uploaded Date: Thursday - May 03rd. 2018 15:34:15 PM. Category: Bedroom. Image Source: freshome.com.
Tap The Thumbnail Bellow to See Related Gallery of "Red And Black King Size Comforter Sets ChoozOne Inside Set Prepare 4"


Casas blancas cielos azules is a series of large-scale digital collages utilizing architectural photographs as well cyanotype reproductions of pencil-line drawings of traditional Islamic patterns from the Maghreb (Morocco, Algeria and Andalusian Spain) .
A North African city, built by the French with a spanish name, Casablanca once the dream of empire it is now the financial capital of Morocco spearheading the dream of modernisation and development. Tension between the drive towards modernity and the desire to hold on to tradition is strongly felt there.
Fragments of these white buildings are taken, mirrored and repeated using the same principles applied in tradition Islamic design. The process abstracts the buildings from their original form. There are hints of their previous identity, but these are not easily recognisable.
This new entity floats in front of blueprint reproductions of pencil-line drawings of traditional Islamic patterns. These patterns form a kind of grid structure that holds the buildings in place. The use of cyanotype with its past application as a means of reproducing architectural plans, alludes to the traditions that underpin and stabilise the fabric of society.
These hand made blue prints are replicas of Moroccan patterns found in Fez. They been created by first drawing the pattern in graphite pencil to create a negative. This negative is then used to print a cyanotype image on cotton fabric. This process is repeated and the panels are then stitched together to create larger pieces.
In these works I have attempted to not only recreate the pattern but to capture the texture and quality of the different mediums used to render them. The hard flat surface of the zelij (mosaic), the softness and depth of plaster and wood carvings.
The Masters who created the originals were working within the qualities and limitations of their materials, and I in this series I attempt to capture these renderings working with the qualities and limitations of my own materials.
Cyantopye is one of the oldest, photographic printing processes. Sir John Herschel invented the Cyanotype process in 1842. After his death in 1871 Cyanotype was used as a method of reproducing architectural plans and drawings in the late 1800's and became know as blue print.
While living in Morocco I have worked with several organisations to document their projects, creating both stills and video documentation, along with written articles.
In Australia I documented several art exhibitions, Street Festivals and other live performance events.
The collaboration between the mind and the hand allows ideas to become objects in the world. This is at the heart of what it is to be human, yet we live in a time where the hand made is becoming more and more rarefied.
Sir John Herschel invented the Cyanotype process in 1842. It is the oldest, simplest and safest of all the alternative photographic printing processes.
These five photograms were made while on residency in Morocco using a glass of mint tea at five times of day and exposing under the Moroccan sun.
This non-narrative video work explores the patterns in traditional artisanal life in Morocco today. Drawing from and reflecting on the patterns shared by the artisans, in their daily work, in sounds of their world and in their shared experiences. The piece reflects the rewards of patience to be found in repetitive work as well as the possible end of that type of work for many of the traditional crafts.
Alex Schmidt took inspiration from Gnawa music rhythms and their repetitive nature to create the sound design, which makes up the spine of the piece. This was then overlayed with interviews conducted in a style inspired by those used to conduct UX Research.
Using photographs and video taken by me Cat Wilson and French photographer Sonia Hamsa, Alex also did most of the editing of the visual component of the piece. The images and footage were captured over several weeks during visits to the studios and workshops of the artisans.
There are no Words – Under Construction was a public program event held at the National Gallery of Victoria as part of Melbourne Now in January and February 2014.
Over two days participants could stitch around the text on 'flash cards' and also to create statements using the cards in a process captured through time-lapse photography.
After the success of the NGV Melbourne Now Public Programs Michelle and I were invited to be a part of the City of Greater Dandenong's Cultural Threads Festival. In June we held a workshop with the Australian Hazara Woman's Friendship Network, stitching and making photo strips from the tapestry flashcards. It was a wonderful day and very inspiring to see what the woman produced.
This video capturing the events of the day played on the Dandenong Civic Square Big Screen from Thursday 31 July to Sunday 31 August 2014.
From 2012 - 2015 I was Exhibitions Project Coordinator at the Australian Centre for the Moving Image having worked on several major shows such 'Shaun Tan's the Lost Thing: From Book to Film', 'Hollywood Costume', and most recently 'DreamWorks Animation: The Exhibition'. Previously I have held positions at ACMI as an installation technician working on over 16 shows and as Acting Registrar (2009-2010) on the shows 'Len Lye, Setting the Scene' and 'Dennis Hopper and the New Hollywood'.
Drawing upon the tradition of early chrono-photographers Eadweard Muybridge and Etienne-Jules Marey. My approach was to use the camera as a technical instrument of observation; to devise a process with which to capture motion through time and reveal to the eye what is always there but not easily apparent. My hope is that the artifact produced extends beyond detached observation and captures something of the beauty of the moon, the place, the time.
A small homage to Muybridge, an opportunity to dissect a photograph tone by tone and put it back together.
I wanted to see what would be revealed if I paid close attention to this small overlooked corner of my neighbourhood, so set myself the task of observing it closely over the course of a year. Every week I photographed the tree at the same time of day and once for each of the four seasons I made a time-lapse over 24 hours. This exercise opened up considerations of bigger universal experiences such as the movement of the planet around the sun and questions about the nature of time.
During the year of shooting my regular presence drew attention to the beautiful tree and the unrealised potential of this vacant lot. Transition Darebin became interested in the location and in 2010 they organised several working bees, which resulted in a garden being planted. Now when you pass the site you will regularly see people sitting enjoying the shade of the tree and what was once an abandoned lot has become a communal space for locals to use and enjoy.
I kept this weekly blog during the making the work of the work and beyond which reflects both my experience and these exciting changes.
In 2014 I started working with Cyanotype. This is a selection of prints made as part of research for two bodies of work I am currently working on using this chemistry.
Whilst I do not specialize in Wedding photography I have been lucky enough to be asked to photograph a few. I like to take a candid approach, avoid set up shots and capture the mood and flavour of the day.
We have produced more plastic in the late decade than in the entire previous century.
A Time-lapse captures the memory of two meadows, one reclaimed plastic the other grass. Then the virtual is projected onto the actual and we see the natural overcome and reclaim the artificial.
"Men go and come, but earth abides."
Dangling Carrots consisted of large tapestries by Michelle Hamer, of signage within everyday suburbia, accompanied by smaller tapestries of 'No Road' signage. Taken at different suburban edge locations these signs literally mark edges and raise personal questions of how to proceed when life appears to be a series of challenges. The 'No Road' works indicate both the end and momentary boundaries of Melbourne housing developments.
I produced a series of videos which documented the prodcution of the 'No Road' tapestries. Every half hour spent stitching was crafted into a loop and then stitched into footage taken of the original source location. these vidoes were then projected on to screens made out of white wool stitched using the same technique as the Michelle's tapastries.
Following my graduation from the VCA School of Drama in 2003 I worked closely with Australian writers to direct and produce five works of new Australian writing in the years 2004-2009. Here is a selection of some of the work that I did during that time.