# On the Boolean Closure of Deterministic Top-Down Tree Automata

Christof Löding  Wolfgang Thomas<EMAIL_ADDRESS>aachen.de$\\}$ RWTH Aachen University, Informatik 7, Aachen, Germany

###### Abstract

The class of Boolean combinations of tree languages recognized by
deterministic top-down tree automata (also known as deterministic root-to-
frontier automata) is studied. The problem of determining for a given regular
tree language whether it belongs to this class is open. We provide some
progress by two results: First, a characterization of this class by a natural
extension of deterministic top-down tree automata is presented, and as an
application we obtain a convenient method to show that certain regular tree
languages are outside this class. In the second result, it is shown that, for
fixed $k$, it is decidable whether a regular tree language is a Boolean
combination of $k$ tree languages recognized by deterministic top-down tree
automata.

###### keywords:

regular tree languages; top-down tree automata; MSO logic.

##  1 Introduction

In the theory of finite automata over finite trees, the principal model is the
“bottom-up” (or “frontier-to-root”) tree automaton; in either its
deterministic or nondeterministic version it serves to characterize the
“regular tree languages”. It is well-known that the nondeterministic “top-
down” (or“root-to-frontier”) tree automata are of the same expressive power
whereas the deterministic ones are strictly weaker. In the sequel we shall
call the latter deterministic top-down tree automata (DTDA) and denote the
class of tree languages recognized by them ${\cal T}(\rm{DTDA})$.

The expressive power of DTDA is well understood. For this purpose one extracts
from a tree $t$ the set $\mathit{paths}(t)$ of finite paths in $t$ from root
to frontier (in a natural way described in detail below) and thus gets, for a
tree language $T$, the set $\mathit{paths}(T)=\bigcup\\{\mathit{paths}(t)\mid
t\in T\\}$. Then a regular tree language $T$ is recognizable by a DTDA iff $T$
is fixed by $\mathit{paths}(T)$ in the sense that

$t\in T\ \ \mbox{iff}\ \ \mathit{paths}(t)\subseteq\mathit{paths}(T).$ ($*$)

A closer analysis of $(*)$ shows that recognizability of a regular tree
language by a DTDA is decidable (cf. Viràgh [12]). The proof of this result
also appears in the first (and up to this time) only monograph on tree
automata [3] by Gecseg and Steinby. As one of the founders of the theory of
tree automata, Magnus Steinby has contributed numerous substantial results to
this subject, among them several results on deterministic top-down tree
automata (see, e.g. [2] and [6]). It is our pleasure and honor to devote this
paper to the memory of Magnus, a great colleague and friend.

DTDA are very limited in expressive power. The class $\cal{T}({\rm DTDA})$ is
neither closed under union nor under complement. This is apparent already from
a very simple example tree language that is not DTDA-recognizable, namely the
two element set $T_{0}=\\{f(a,b),f(b,a)\\}$ (using the term notation for
trees). If $T_{0}$ was DTDA-recognizable, then invoking $(*)$ also the trees
$f(a,a)$ and $f(b,b)$ would belong to $T_{0}$, a contradiction.

In order to overcome this weakness of DTDA, several extensions of the class of
DTDA-recognizable tree languages (within the class of regular tree languages)
have been considered, among them the closure of ${\cal T}({\rm DTDA})$ under
Boolean operations [4] and the class of tree languages recognized by DTDA with
“regular frontier-check” [5]. In the present paper we study the Boolean
closure of ${\cal T}({\rm DTDA})$, denoted ${\rm Bool}({\cal T}({\rm DTDA}))$,
extending the work of Jurvanen [4]. A major problem, open now for several
decades, is to show the analogue of Virágh’s result mentioned above, i.e., to
show that membership of a regular tree language in ${\rm Bool}({\cal T}({\rm
DTDA}))$ is decidable (or to show the unlikely opposite – that it is
undecidable).

While leaving open this question, the present paper offers two results that
provide some progress. First we present a natural model of automaton (“DTDA
with set acceptance”) that characterizes ${\rm Bool}({\cal T}({\rm DTDA}))$
and permits simple proofs that certain regular tree languages do not belong to
this class. Second, we provide a decision procedure for subclasses of ${\rm
Bool}({\cal T}({\rm DTDA}))$, where only a bounded number of Boolean
operations is admitted on top of ${\cal T}({\rm DTDA})$. More precisely, we
consider, for $k\geq 1$, the class $k$-${\rm Bool}({\cal T}({\rm DTDA}))$,
containing the tree languages that are Boolean combinations of $k$ tree
languages from ${\cal T}({\rm DTDA})$. We show that for each $k\geq 1$,
membership of a regular tree language in the class $k$-${\rm Bool}({\cal
T}({\rm DTDA}))$ is decidable.

Let us mention three papers on related work.

In [4], Eija Jurvanen provided the first study of the class ${\rm Bool}({\cal
T}({\rm DTDA}))$, showing algebraic properties and giving first examples of
regular tree languages outside this class. Using the DTDA with set acceptance
of the present paper we get such examples without entering complex
combinatorial calculations as they appear in [4].

In his PhD thesis [1] of Mikolaj Bojaǹzcyk obtained a characterization of
${\rm Bool}({\cal T}({\rm DTDA}))$ in terms of word sum automata, which are
deterministic bottom-up tree automata derived from word automata for paths.
Our model of DTDA with set acceptance has the advantage of being a direct
generalization of DTDA in which proofs of non-membership in ${\rm Bool}({\cal
T}({\rm DTDA}))$ are straightforward.

Finally, we mention the recent paper [7] of P. Leupold and S. Maneth in which
– among other results – decidability of a subclass of ${\rm Bool}({\cal
T}({\rm DTDA}))$ is claimed, namely of the class of finite unions of tree
languages in ${\cal T}({\rm DTDA})$. Since Lemma 5 of that paper is not valid
(as a counter-example shows), this decidability claim seems open to us (parts
of the results from [7] have been fixed in [8], but this does not include the
decidability of the class of finite unions of tree languages in ${\cal T}({\rm
DTDA})$.)

##  2 Preliminaries

Ranked trees are terms composed from symbols of a ranked alphabet, which is a
finite set of symbols where each symbol has a fixed rank, a natural number
that indicates the arity of this symbol. Thus symbols of rank $k>0$ can be
considered as function symbols of arity $k$ and symbols of rank 0 as
constants. We denote a ranked alphabet by the letter $\Sigma$, the rank of
symbol $a$ as $|a|$, and the set of symbols of $\Sigma$ of rank $i$ by
$\Sigma_{i}$. Ranked trees over $\Sigma$ are also called $\Sigma$-trees. The
set $\mathcal{T}_{\Sigma}$ of $\Sigma$-trees is defined inductively by the two
clauses that each symbol $c\in\Sigma_{0}$ belongs to $\mathcal{T}_{\Sigma}$
and that with $t_{1},\ldots,t_{i}\in\mathcal{T}_{\Sigma}$ and $f\in\Sigma_{i}$
also $f(t_{1},\ldots,t_{i})$ belongs to $\mathcal{T}_{\Sigma}$.

It is convenient to use also a graphical representation (as the word “tree”,
rather than “term”, suggests). Here a tree consists of nodes that are labelled
with letters from $\Sigma$. Formally, for a tree $t$ we introduce its domain
$\mathit{dom}(t)\subseteq\mathbb{N}^{*}$. If the tree is a constant then this
domain just contains $\varepsilon$; if $t=a(t_{1},\ldots,t_{k})$ with $k>0$
then
$\mathit{dom}(t)=\\{\varepsilon\\}\cup\bigcup_{i=1}^{k}i\cdot\mathit{dom}(t_{i})$,
where $\cdot$ is the concatenation of words. We say that $\varepsilon$ is the
root, that a node $u$ with a symbol of rank $k>0$ has $u1,\ldots,uk$ as its
children, that nodes without children are leaves, and that non-leaf-nodes are
inner nodes. A tree $t$ over $\Sigma$ can then be presented as a map
$t:\mathit{dom}(t)\rightarrow\Sigma$. The nodes of $\mathit{dom}(t)$ without
successors in $\mathit{dom}(t)$ form the “frontier” of $t$; this set is
denoted ${\rm fr}(f)$. Sometimes we also use successors of frontier nodes and
call them nodes of the “outer frontier”. We set ${\rm fr}^{+}(t):=\\{u1\mid
u\in{\rm fr}(t)\\}$ and $\mathit{dom}^{+}(t):=\mathit{dom}(t)\cup{\rm
fr}^{+}(t)$.

Now we recall the standard concepts of deterministic tree automata in the two
versions “bottom-up” and “top-down”.

A deterministic bottom-up tree automaton over
$\Sigma=\bigcup_{i=0}^{r}\Sigma_{i}$ is of the form
$\mathcal{A}=(Q,\delta,F)$, where $Q$ is the finite set of states, $F\subseteq
Q$ is the set of “final” (or “accepting”) states, and $\delta$ the transition
function, given as the union of functions
$\delta_{i}:Q^{i}\times\Sigma_{i}\rightarrow Q$ for $i=0,\ldots,r$. Here
$\delta_{0}$ is considered as a function from $\Sigma_{0}$ to $Q$. We define,
for any tree $t$ over $\Sigma$, the state $\delta_{\mathcal{A}}(t)$
inductively, by setting, for $a\in\Sigma_{0}$,
$\delta_{\mathcal{A}}(a):=\delta_{0}(a)$, and for $a\in\Sigma_{i}$ where
$i\in\\{1,\ldots,r\\}$,
$\delta_{\mathcal{A}}(a(t_{1},\ldots,t_{i})):=\delta_{i}(\delta_{\mathcal{A}}(t_{1}),\ldots,\delta_{\mathcal{A}}(t_{i}),a)$.
The tree $t$ is accepted by $\mathcal{A}$ if $\delta_{\mathcal{A}}(t)\in F$,
and the tree language recognized by $\mathcal{A}$ is $T(\mathcal{A})=\\{t\in
T_{\Sigma}\mid t\mbox{ is accepted by }\mathcal{A}\\}$. The tree languages
recognized by bottom-up tree automata are the “regular” ones.

A deterministic top-down tree automaton (DTDA) over the ranked alphabet
$\Sigma=\bigcup_{i=0}^{r}\Sigma_{i}$ is of the form
$\mathcal{A}=(Q,q_{0},\delta,F)$ where $Q$ is the finite set of states,
$q_{0}\in Q$, $F\subseteq Q$, and $\delta$ again given as the union of
functions $\delta_{i}$ ($i\in\\{0,\ldots,r\\}$), now with
$\delta_{i}:Q\times\Sigma_{i}\rightarrow Q^{i}$ for $i\in\\{1,\ldots,r\\}$ and
$\delta_{0}:Q\times\Sigma_{0}\rightarrow Q$. We define the function
$\delta_{\mathcal{A}}:Q\times T_{\Sigma}\rightarrow 2^{Q}$, associating with
each tree $t$ the “set of states reached by $\mathcal{A}$ from $q$ via $t$ at
the outer frontier”, as follows: If $t=a\in\Sigma_{0}$ then
$\delta_{\mathcal{A}}(q,t)=\\{\delta_{0}(q,a)\\}$. If
$t=a(t_{1},\ldots,t_{i})$, say with $\delta_{i}(q,a)=(q_{1},\ldots,q_{i})$,
then
$\delta_{\mathcal{A}}(q,t)=\delta_{\mathcal{A}}(q_{1},t_{1})\cup\ldots\cup\delta_{\mathcal{A}}(q_{i},t_{i})$.
The automaton $\mathcal{A}$ accepts $t$ if
$\delta_{\mathcal{A}}(q_{0},t)\subseteq F$. As already said in the
introduction, we denote by ${\cal T}({\rm DTDA})$ the class of tree languages
recognized by DTDA.

The behaviour of DTDA can best be understood in terms of the runs over the
given input trees. Here we refer to the “graphical” presentation of trees and
associate with any node $u$ of $\mathit{dom}^{+}(t)$ the state reached at $u$
by the automaton under consideration. Contrary to the case of bottom-up
automata, the run of a DTDA can be built up “path-wise”: To determine the
state at node $u$ it suffices to follow the path from the root to $u$ and
apply the transition function of the automaton restricted to this path. Let us
describe this well-known observation in precise terms.

A (labeled) path over a ranked alphabet $\Sigma$ is a finite word of the form
$\pi=a_{1}d_{1}a_{2}d_{2}\cdots a_{n}d_{n}a_{n+1}$ where

  * •

$a_{i}\in\Sigma$ for all $i\in\\{1,\ldots,n+1\\}$,

  * •

$d_{i}\in\\{1,\ldots,|a_{i}|\\}$ for all $i\in\\{1,\ldots,n\\}$, and

  * •

$a_{n+1}\in\Sigma_{0}$.

So $\pi$ alternates between labels and possible directions in the tree, ending
with a leaf label. We denote the alphabet for paths by $\Gamma$, so

$\Gamma:=\Sigma\cup D\text{ with $D:=\\{1,\ldots,r\\}$}$

where $r$ is the maximal rank of a symbol in $\Sigma$.

For a tree $t$ over $\Sigma$ we denote by
$\mathit{paths}(t)\subseteq\Gamma^{*}$ the set of all labeled paths in $t$.
For example, let $\Sigma_{2}=\\{a,b\\}$, $\Sigma_{0}=\\{c,d\\}$, and $t$ be
the left-most tree in Figure 1, that is, $t=a(b(c,d),c)$. Then
$\mathit{paths}(t)=\\{a1b1c,a1b2d,a2c\\}$. We lift this to sets of trees by
defining $\mathit{paths}(T):=\bigcup_{t\in T}\mathit{paths}(t)$.

Vice versa, if we are given a set $P$ of labeled paths, then we define

$\mathit{trees}(P):=\\{t\in\mathcal{T}_{\Sigma}\mid\mathit{paths}(t)\subseteq
P\\}$

to be the set of all trees that can be built from paths in $P$. An example is
shown in Figure 1.

$a$$b$$c$$d$$c$$a$$b$$c$$d$$d$$a$$a$$d$$c$$c$$a$$a$$d$$c$$d$ Figure 1: The set
$\mathit{trees}(P)$ for $P=\\{a1b1c,a1b2d,a1a1d,a1a2c,a2c,a2d,b2c\\}$. Note
that the path $b2c$ is in $P$ but does not occur in any of the trees because
no tree with $b$ at the root can be built from paths in $P$.

The following theorem characterizes DTDA-recognizable languages in terms of
paths.

######  Theorem 2.1 ([12]).

A tree language $T$ over $\Sigma$ is DTDA-recognizable iff
$T=\mathit{trees}(P)$ for a regular set $P\subseteq\Gamma^{*}$ of paths.

##  3 Automata with Set Acceptance

We recall that a DTDA $\mathcal{A}=(Q,q_{0},\delta,F)$ accepts a tree $t$ if
$\delta_{\mathcal{A}}(t)\subseteq F$, i.e., all states reached in the run of
$\mathcal{A}$ over $t$ at the outer frontier belong to $F$. A DTDA with set
acceptance will make more detailed use of the set $R$ of states reached at the
outer frontier of the tree under consideration. In a standard DTDA this set
should satisfy $R\subseteq F$. We shall allow also a dual condition, requiring
that some state of $F$ is reached, which can be phrased as $R\cap
F\not=\emptyset$ with $R$ specified as above. More generally, we shall allow
an acceptance requirement for any combination on the existence or non-
existence of states of $Q$. In other words, we allow for any subset $F$ of $Q$
the requirement that $\delta_{\mathcal{A}}(t)=F$, i.e., that precisely the
states of $F$ are reached at the outer frontier. Collecting those $F$ which
are admitted in this sense for acceptance of a tree, we obtain a family
$\mathcal{F}$ of state sets as a new kind of acceptance component of DTDA.

In the remainder of this section we only consider binary alphabets of the form
$\Sigma=\Sigma_{0}\cup\Sigma_{2}$. We make this assumption for notational
simplicity, the results hold for arbitrary ranked alphabets.

A DTDA with set acceptance over the ranked alphabet $\Sigma$ is of the form
${\cal A}=(Q,q_{0},\delta,{\cal F})$ where $q_{0}$ and $\delta$ are as for
DTDA and where ${\cal F}\subseteq 2^{Q}$ is a family of state sets over $Q$.
The automaton ${\cal A}$ accepts the tree $t$ if
$\delta_{\mathcal{A}}(q_{0},t)\in{\cal F}$.

This type of acceptance condition is familiar from the theory of automata over
infinite words and called there Muller condition (introduced in [9]); an
infinite run is declared accepting if the states occurring infinitely often in
it form a set that belongs to ${\cal F}$.

Let us mention some immediate properties and examples of DTDA with set
acceptance. First, as expected, the standard DTDA can be considered as a
special case:

######  Remark 3.1.

Each DTDA can be presented as a DTDA with set acceptance.

Consider a DTDA ${\cal A}=(Q,q_{0},\delta,F)$ and observe that the tree
automaton ${\cal A}^{\prime}=(Q,q_{0},\delta,\\{R\in 2^{Q}\mid R\subseteq
F\\})$ with set acceptance is equivalent to ${\cal A}$.

We recall that a singleton tree language $\\{t\\}$ can be recognized by a DTDA
with a singleton set $F=\\{q_{+}\\}$ as acceptance component: A corresponding
DTDA has, besides the accepting state $q_{+}$ and the rejecting state $q_{-}$,
one state for each symbol occurrence in $t$. We denote the different
occurrences of symbol $a$ by $a^{i}$ for different numbers $i$ and denote by
$q_{a^{i}}$ the corresponding states. If the top symbol of $t$ is the symbol
occurrence $a^{i}$ we take $q_{a^{i}}$ as initial state $q_{0}$. If in $t$ the
triple $a^{i}(b^{j},c^{k})$ of symbol occurrences appears (where
$a\in\Sigma_{2}$), we set $\delta_{2}(q_{a^{i}},a)=(q_{b^{j}},q_{c^{k}})$, and
for a symbol occurrence $a^{i}$ with $a\in\Sigma_{0}$ we set
$\delta_{0}(q_{a^{i}},a)=q_{+}$; in all other cases we take $(q_{-},q_{-})$,
respectively $q_{-}$, as value. It is clear that this DTDA recognizes the set
$\\{t\\}$. Proceeding to DTDA with set acceptance, we use the same automaton,
but taking as acceptance component the singleton family $\\{\\{q_{+}\\}\\}$.
So we have the following remark:

######  Remark 3.2.

A singleton tree language is recognized by

  * •

a DTDA with a singleton as acceptance component,

  * •

a DTDA with set acceptance whose acceptance component is a singleton
consisting of a singleton.

Next we verify that DTDA with set acceptance allow for closure under Boolean
operations:

######  Proposition 3.3.

The class of tree languages recognized by DTDA with set acceptance (over a
fixed ranked alphabet) is closed under Boolean operations.

######  Proof 3.4.

It suffices to consider complementation and union. The proof is
straightforward; we only give the definition of the required automata.

Given the tree automaton ${\cal A}=(Q,q_{0},\delta,{\cal F})$ with set
acceptance, we may take ${\cal A}^{\prime}=(Q,q_{0},\delta,2^{Q}\setminus{\cal
F})$ as the complement automaton of ${\cal A}$. Given two DTDA ${\cal
A}_{1}=(Q_{1},q^{1}_{0},\delta^{1},{\cal F}^{1})$ and ${\cal
A}_{2}=(Q_{2},q^{2}_{0},\delta^{2},{\cal F}^{2})$ with set acceptance (and
where $\delta^{i}=\delta^{i}_{0}\cup\delta^{i}_{2}$), the following DTDA with
set acceptance recognizes $T({\cal A}_{1})\cup T({\cal A}_{2})$:

${\cal A}^{\prime}=(Q_{1}\times
Q_{2},(q^{1}_{0},q^{2}_{0}),\delta^{\prime},{\cal F}^{\prime})$

where $\delta^{\prime}=\delta^{\prime}_{0}\cup\delta^{\prime}_{2}$ with the
definitions
$\delta^{\prime}_{0}((p,q),a)=(\delta^{1}_{0}(p,a),\delta^{2}_{0}(q,a))$ and,
using the projections $\pi_{1},\pi_{2}$ with $\pi_{1}(p,q)=p$ and
$\pi_{2}(p,q)=q$,

$\delta^{\prime}_{2}((p,q),a)=((\pi_{1}(\delta^{1}_{2}(p,a)),\pi_{1}(\delta^{2}_{2}(q,a))),(\pi_{2}(\delta^{1}_{2}(p,a)),\pi_{2}(\delta^{2}_{2}(q,a))))$

Finally, we define ${\cal F}^{\prime}$ by specifying that
$R=\\{(p_{1},q_{1}),\ldots,(p_{k},q_{k})\\}$ belongs to ${\cal F}^{\prime}$
iff $\\{p_{1},\ldots,p_{k}\\}\in{\cal F}^{1}$ or
$\\{q_{1},\ldots,q_{k}\\}\in{\cal F}^{2}$.

As a consequence of Remark 3.2 and Proposition 3.3, we see that each finite
tree language $\\{t_{1},\ldots,t_{n}\\}$ (and hence also each co-finite tree
language) is recognizable by a DTDA with set acceptance. As mentioned above,
standard DTDA fail to recognize the two-element tree language
$\\{f(a,b),f(b,a)\\}$; so we have shown that the expressive power of DTDA with
set acceptance properly exceeds that of DTDA.

Next we verify that DTDA with set acceptance characterize the Boolean closure
of ${\cal T}({\rm DTDA})$. Intuitively speaking, we see that adding Boolean
logic on the occurrence of states to the acceptance condition of DTDA (i.e.,
“inside” DTDA) amounts to the same as adding Boolean logic to the tree
languages recognized by DTDA (i.e., “outside” DTDA).

######  Proposition 3.5.

A tree language $T$ is recognized by a DTDA with set acceptance iff T belongs
to ${\rm Bool}({\cal T}({\rm DTDA}))$.

######  Proof 3.6.

The direction from right to left is clear from Remark 3.1 and Proposition 3.3.

For the direction from left to right, consider a tree automaton ${\cal
A}=(Q,q_{0},\delta,{\cal F})$ with set acceptance. Let ${\cal
F}=\\{F_{1},\ldots,F_{k}\\}$. Then the tree language recognized by ${\cal A}$
is the union of the tree languages recognized by the DTDA ${\cal
A}_{i}=(Q,q_{0},\delta,\\{F_{i}\\})$. So it suffices to show that a DTDA of
the simple form ${\cal B}=(Q,q_{0},\delta,\\{F\\})$ with set acceptance
recognizes a tree language in ${\rm Bool}({\cal T}({\rm DTDA}))$. Now ${\cal
B}$ accepts a tree $t$ if

  * •

each state reached via some path in the unique run of ${\cal B}$ on $t$
belongs to $F$, and that conversely

  * •

each $F$-state is reached via some path in the unique run of ${\cal B}$ on
$t$.

So $T({\cal B})$ is the intersection of the tree language recognized by the
DTDA $(Q,q_{0},\delta,F)$ and, writing $F=\\{q_{1},\ldots,q_{r}\\}$, of the
intersection of the tree languages $T_{q_{i}}$ where $T_{q_{i}}$ contains the
trees on which the given DTDA reaches $q_{i}$ somewhere at the outer frontier.
Now $T_{q_{i}}$ belongs to ${\rm Bool}({\cal T}({\rm DTDA}))$ since the
complement of $T_{q_{i}}$ is recognized by the standard DTDA
$(Q,q_{0},\delta,Q\setminus\\{q_{i}\\})$.

As an application of Proposition 3.5, we present examples of regular tree
languages that are outside ${\rm Bool}({\cal T}({\rm DTDA}))$.

DTDA with set acceptance can check trees for the existence or the non-
existence of paths (with regular properties) but this does not cover
conditions on the number of occurrences of paths or on the (left-to-right)
order of different paths. As we shall show, these properties of (or relations
between) paths take us outside ${\rm Bool}({\cal T}({\rm DTDA}))$. Regarding
the aspect of ordering, we say that symbol $a$ occurs left to symbol $b$ in a
tree if $a$ and $b$ are the labels of two nodes $u$ and $v$ such that for the
last common ancestor $w$ of them $u$ belongs to the left subtree of $w$ and
$v$ to the right subtree of the node $w$.

######  Proposition 3.7.

Let $\Sigma=\Sigma_{2}\cup\Sigma_{0}$ with $\Sigma_{2}=\\{a\\}$ and
$\Sigma_{0}=\\{c,d,e\\}$ and

  * •

$T_{1}=\\{t\in\mathcal{T}_{\Sigma}\mid d\mbox{ occurs only once in }t\\}$,

  * •

$T_{2}=\\{t\in\mathcal{T}_{\Sigma}\mid d\mbox{ occurs left of }\ e\mbox{ in
}t\\}$.

Neither $T_{1}$ nor $T_{2}$ belong to ${\rm Bool}({\cal T}({\rm DTDA}))$.

######  Proof 3.8.

In both cases we proceed in the same way: Given a DTDA with set acceptance
$\mathcal{A}_{1}$ recognizing $T_{1}$ we present a tree $t_{1}\in T_{1}$ such
that a modification of it is outside $T_{1}$ but still accepted by
$\mathcal{A}_{1}$; similarly for a DTDA with set acceptance $\mathcal{A}_{2}$
recognizing $T_{2}$ and a suitable tree $t_{2}\in T_{2}$.

We start with a “right-comb” where to the root symbol $a$ we attach $n$ times
$a$ as right child, always taking $c$ as the left child, and at the last $a$
finishing with $c$ as left and right child. When increasing $n$, the automaton
$\mathcal{A}_{1}$ assumes an ultimately periodic sequence of states on the
branch consisting of the letters $a$, say finishing the initial part of this
state sequence after the $k$-th letter $a$, the first period after the
$(k+p)$-th letter $a$, and the second period after the $(k+2p)$-th letter $a$.

Let $t_{1}$ be the comb-tree with $(k+3p)$ letters $a$, where the left child
of the $(k+1)$-th $a$ is changed from $c$ to $d$. Then $t_{1}\in T_{1}$ and
thus accepted by $\mathcal{A}_{1}$. If we change also left child of the
$(k+p+1)$-th letter $a$ from $c$ to $d$, thus obtaining the tree
$t^{\prime}_{1}$, then $t^{\prime}_{1}\not\in T_{1}$ but by choice of $k$ and
$p$ the same states will occur at the outer frontiers of $t_{1}$ and
$t^{\prime}_{1}$ in the runs of $\mathcal{A}_{1}$ on these trees; so
$\mathcal{A}_{1}$ accepts $t^{\prime}_{1}$. See Figure 2 for an illustration.

$a$$q_{0}$$c$$a$$q_{1}$$c$$a$$q_{k}=q$$d$$a$$q_{k+p}=q$$c/d$$a$$q_{k+2p}=q$$c$$a$$q_{k+3p}$$c$$c$
Figure 2: Illustration for the proof of Proposition 3.7. All inner nodes of
the tree are labeled with $a$. All leaves not shown in the illustration are
labeled with $c$.

Given $\mathcal{A}_{2}$ we again take the comb-trees mentioned above and
define $k$ and $p$ analogously. Let $t_{2}$ be the comb-tree with $(k+3p)$
letters $a$, where the left child of the $(k+1)$-th $a$ is changed from $c$ to
$d$ and the left child of the $(k+p+1)$-th $a$ is changed from $c$ to $e$.
Then $t_{2}\in T_{2}$, thus accepted by $\mathcal{A}_{2}$. If we now change
the left child of the $(k+1)$-th letter $a$ back to $c$, not touching the $e$
at the left child of the $(k+p+1)$-th letter $a$, but changing the left child
of the $(k+2p+1)$-th letter $a$ from $c$ to $d$, then we obtain a tree
$t_{2}^{\prime}$ outside $T_{2}$ but again by choice of $k$ and $p$ the same
states will occur at the outer frontier of $t_{2}$ and $t^{\prime}_{2}$ in the
run of $\mathcal{A}_{2}$ on these trees, and thus $\mathcal{A}_{2}$ accepts
$t_{2}^{\prime}$.

We add a remark regarding the DTDA with regular frontier-check from [5],
mentioned in Section 1. For the acceptance of input trees, such a DTDA
$\mathcal{A}$ (say with state set $Q$) is equipped with a standard finite
automaton $\mathcal{B}$ on words whose input alphabet is $Q$. A tree $t$ is
accepted by $\mathcal{A}$ if the sequence of states reached by $\mathcal{A}$
on the outer frontier $fr^{+}(t)$, read from left to right, is accepted by
$\mathcal{B}$. The DTDA with set acceptance correspond to the special case
where the automata $\mathcal{B}$ only record the sets of states from $Q$ that
occur in given sequences over $Q$. The two tree languages $T_{1},T_{2}$ of
Proposition 6 are easily seen to be recognizable by DTDA with regular
frontier-check, thus showing in a simpler way than in [5] that ${\rm
Bool}({\cal T}({\rm DTDA}))$ is a proper subclass of the class of tree
languages recognized by DTDA with regular frontier-check.

##  4 Decidability of Membership in $k$-${\rm Bool}({\cal T}({\rm DTDA}))$

In this section, we show that it is decidable whether a given regular tree
language $T$ is a Boolean combination of at most $k$ deterministic top-down
languages for a given $k$. We achieve this by invoking a decidability result
on monadic second-order logic (MSO logic), namely that the MSO-theory of the
infinite tree of given finite branching is decidable. We assume that the
reader is acquainted with the basics of MSO logic (as given, e.g., in [11]).

We make use of the characterization of deterministic top-down languages in
terms of their paths as given in Theorem 2.1, which implies that we can encode
DTDA-recognizable tree languages over $\Sigma$ by subsets of $\Gamma^{*}$
(recall that $\Gamma=\Sigma\cup D$ with $D=\\{1,\ldots r\\}$ where $r$ is the
maximal rank of symbols in $\Sigma$). The following characterization of
membership in $k$-${\rm Bool}({\cal T}({\rm DTDA}))$ provides the bridge to
MSO logic, more precisely to MSO logic over the infinite $|\Gamma|$-branching
tree:

######  Lemma 4.1.

A tree language $T$ is in $k$-${\rm Bool}({\cal T}({\rm DTDA}))$ iff there are
regular sets $P_{1},\ldots,P_{k}\subseteq\Gamma^{*}$ such that for all trees
$t,t^{\prime}\in\mathcal{T}_{\Sigma}$ with $t\in T$ and $t^{\prime}\notin T$,
there exists $i\in\\{1,\ldots,k\\}$ such that $(\mathit{paths}(t)\subseteq
P_{i})\Leftrightarrow(\mathit{paths}(t^{\prime})\not\subseteq P_{i})$.

######  Proof 4.2.

For the left-to-right direction, assume that $T$ is in $k$-${\rm Bool}({\cal
T}({\rm DTDA}))$. Then $T$ is a Boolean combination of DTDA-recognizable
languages $T_{1},\ldots,T_{k}$. Let $P_{1},\ldots,P_{k}\subseteq\Gamma^{*}$ be
regular path languages with $\mathit{trees}(P_{i})=T_{i}$ according to Theorem
2.1. Note that for $t\in\mathcal{T}_{\Sigma}$, $\mathit{paths}(t)\subseteq
P_{i}$ is equivalent to $t\in T_{i}$.

Write the Boolean combination of $T_{1},\ldots,T_{k}$ for $T$ in disjunctive
normal form, that is, as $T=\bigcup_{i}\bigcap_{j}R_{ij}$ where each $R_{ij}$
is one of $T_{1},\ldots,T_{k}$ or a complement of one of $T_{1},\ldots,T_{k}$.

Now let $t,t^{\prime}\in\mathcal{T}_{\Sigma}$ with $t\in T$ and
$t^{\prime}\notin T$. Since $t\in T$, there is an index $i_{0}$ such that
$t\in\bigcap_{j}R_{i_{0}j}$. And since $t^{\prime}\notin T$, there is (for all
$i$, hence for $i_{0}$) an index $h$ such that $t^{\prime}\notin R_{i_{0}h}$.
If $R_{i_{0}h}=T_{\ell}$, then $\mathit{paths}(t)\subseteq P_{\ell}$ and
$\mathit{paths}(t^{\prime})\not\subseteq P_{\ell}$. If $R_{i_{0}h}$ is the
complement of $T_{\ell}$, then $\mathit{paths}(t)\not\subseteq P_{\ell}$ and
$\mathit{paths}(t^{\prime})\subseteq P_{\ell}$.

For the right-to-left direction, assume that
$P_{1},\ldots,P_{k}\subseteq\Gamma^{*}$ exist as in the claim of the lemma.
Let $T_{i}$ be the set of trees $t$ with $\mathit{paths}(t)\subseteq P_{i}$
and choose $R_{1},\ldots,R_{k}$ such that each $R_{i}$ is either $T_{i}$ or
the complement of $T_{i}$. Then for all trees
$t,t^{\prime}\in\mathcal{T}_{\Sigma}$ with $t\in T$ and $t^{\prime}\notin T$,
there exists $i\in\\{1,\ldots,k\\}$ such that $t\in R_{i}$ iff
$t^{\prime}\notin R_{i}$. Hence, $R_{1}\cap\cdots\cap R_{k}$ is either a
subset of $T$ or has empty intersection with $T$. So we can write $T$ as the
union of those $R_{1}\cap\cdots\cap R_{k}$ that are subset of $T$.

The condition of Lemma 4.1 can be expressed in MSO logic over the infinite
$\Gamma$-tree as we explain in the following.

The (infinite) $\Gamma$-tree is the structure with domain $\Gamma^{*}$ and
binary successor relations $S_{\gamma}$ for each $\gamma\in\Gamma$ with
$S_{\gamma}(u,v)$ if $v=u\gamma$. We also say that $v$ is the
$\gamma$-successor of $u$. The root of the tree is $\varepsilon$. In the
context of the infinite $\Gamma$-tree, we refer to the elements of
$\Gamma^{*}$ as nodes of the tree.

We consider monadic second-order logic (MSO logic) over this structure, which
is first-order logic extended with quantification over sets of nodes, and
atomic formulas $x\in X$ for first-order variables $x$ and set variables $X$.
In general, set variables are denoted by capital letters, and first-order
variables by lower case letters.

As an example, consider the following formula with two free first-order
variables $x,y$ that expresses that $x$ is a prefix of $y$. The formula uses a
set quantifier for the variable $X$. We use $S(z,z^{\prime})$ as an
abbreviation for $\bigvee_{\gamma\in\Gamma}S_{\gamma}(z,z^{\prime})$, which
means that $z^{\prime}$ is some successor of $z$.

$\forall X\;(y\in X\land\forall z,z^{\prime}\;(S(z,z^{\prime})\land
z^{\prime}\in X\rightarrow z\in X))\rightarrow x\in X$

This formula states that all sets that contain $y$ and are closed under
predecessors also contain $x$, which means that $x$ is a prefix of $y$. For
more details on MSO logic over infinite trees, in particular the following
theorem, see [11]:

######  Theorem 4.3 ([10]).

It is decidable whether a given MSO formula $\varphi(X_{1},\ldots,X_{k})$ over
the $\Gamma$-tree is satisfiable. Furthermore, if the formula is satisfiable,
one can construct regular subsets $P_{1},\ldots,P_{k}$ of $\Gamma^{*}$ that
make $\varphi$ true if each $X_{i}$ is interpreted as $P_{i}$.

We now explain how to express the condition from Lemma 4.1 in MSO (without
giving all the details). Recall that labeled paths are elements of
$\Gamma^{*}$, so they correspond to elements of the $\Gamma$-tree. One can
easily write a formula $\varphi_{\mathrm{pth}}(x)$ that is true iff the node
$x$ corresponds to a labeled path. The formula just needs to express that on
the prefixes of $x$, the successors alternate between $\Sigma$ and $D$,
starting with $\Sigma$, ending with $\Sigma_{0}$, and the $D$-successors match
with the arity of the previous $\Sigma$-successor.

For every tree $t\in\mathcal{T}_{\Sigma}$, we have that
$\mathit{paths}(t)\subseteq\Gamma^{*}$. We say that a set
$U\subseteq\Gamma^{*}$ of nodes encodes a tree if $U=\mathit{paths}(t)$ for
some tree $t$. Using $\varphi_{\mathrm{pth}}(x)$, it is not very difficult to
write a formula $\varphi_{\mathrm{tr}}(X)$ that expresses that the set $X$
encodes a tree. Such a formula needs to ensure that $X$ is non-empty, only
contains elements that correspond to labeled paths, and the prefix closure
$X^{\prime}$ of $X$ has the following properties: (1) if $x\in X^{\prime}$
ends in a letter $a\in\Sigma_{i}$, then $xj\in X^{\prime}$ iff
$j\in\\{1,\ldots,i\\}$, and (2) if $x\in X^{\prime}$ ends in a direction $j\in
D$, then there is a unique $a\in\Sigma$ with $x^{\prime}a\in X^{\prime}$.

Furthermore, given a regular language $T\subseteq\mathcal{T}_{\Sigma}$ of
trees, there is a formula $\varphi_{T}(X)$ that expresses that $X$ encodes a
tree that is in $T$. Such a formula uses $\varphi_{\mathrm{tr}}(X)$, and
furthermore expresses the existence of an accepting run of an automaton for
$T$ on the tree encoded by $X$. The standard translations from finite automata
to MSO (see [11]) can easily be adapted to our encoding of finite tree as
subsets of the $\Gamma$-tree. Similarly, there is a formula $\varphi_{\neg
T}(X)$ that expresses that $X$ encodes a tree that is not in $T$.

Now the condition from Lemma 4.1 can be expressed in MSO by the following MSO
sentence.

$\exists X_{1},\ldots,X_{k}\,\forall
Y,Y^{\prime}\left(\varphi_{T}(Y)\land\varphi_{\neg
T}(Y^{\prime})\rightarrow\bigvee_{i=1}^{k}(Y\subseteq X_{i}\leftrightarrow
Y^{\prime}\not\subseteq X_{i})\right)$

From Theorem 4.3, we can conclude that if this sentence is true, then there
are regular sets $P_{1},\ldots,P_{k}$ for the $X_{i}$ that make the sentence
true. Hence, by Lemma 4.1, the sentence is true iff $T$ is in $k$-${\rm
Bool}({\cal T}({\rm DTDA}))$. By Theorem 4.3, membership of $T$ in $k$-${\rm
Bool}({\cal T}({\rm DTDA}))$ is decidable:

######  Theorem 4.4.

It is decidable for a given regular tree language $T$ and a given number $k$
whether $T$ is a Boolean combination of (at most) $k$ DTDA-recognizable
languages.

##  5 Conclusion

We have shown two results that provide some progress towards an effective
characterization of the Boolean closure of the class of DTDA-recognizable tree
languages. In the first result, we offered an automata-theoretic
characterization; however, this characterization does not permit an effective
decision whether a regular tree language belongs to ${\rm Bool}({\cal T}({\rm
DTDA}))$. In the second result such an effective decision was provided;
however, it refers to a fixed subclass $k$-${\rm Bool}({\cal T}({\rm DTDA}))$
of ${\rm Bool}({\cal T}({\rm DTDA}))$.

We conclude with some remarks on open questions.

In Proposition 3.7 two phenomena are mentioned that cause a regular tree
language to fall outside ${\rm Bool}({\cal T}({\rm DTDA}))$, namely, multiple
occurrence of (properties of) subtrees, and the order between occurrences of
(properties of) subtrees. We may ask whether there are other conditions of
this kind on regular tree languages that also induce non-membership in ${\rm
Bool}({\cal T}({\rm DTDA}))$.

A related track of research is to search for a characterization of ${\rm
Bool}({\cal T}({\rm DTDA}))$ in terms of the transition structure of minimal
bottom-up tree automata (which are determined up to isomorphism for a given
regular tree language). Specifically, one may search for patterns in the
transition function which induce the presence of counting multiplicities of
subtrees or of distinguishing the order of subtrees. We recall that such
“forbidden patterns” are well-known in the classical theory of automata over
finite words. For example, Schützenberger’s Theorem on the characterization of
star-free word languages says that a regular word language $L$ is star-free
iff the minimal deterministic automaton recognizing $L$ is “permutation-free”,
i.e., there is no word $w$ that induces a non-trivial permutation of states of
the automaton (a property that can effectively be decided since $|w|$ can be
bounded in the number of states of the automaton).

The problem of deciding membership of regular tree languages in ${\rm
Bool}({\cal T}({\rm DTDA}))$ can also be phrased in a simpler and direct
manner by asking for certain bounds in the two results of the present paper:
Given a regular tree language $T$ (presented, e.g., in terms of its minimal
bottom-up tree automaton), can one provide a bound $K$ such that $T$ belongs
to ${\rm Bool}({\cal T}({\rm DTDA}))$ iff a DTDA with set acceptance and $\leq
K$ states recognizes $T$? Or, more on the track of Theorem 4.4, can one
determine some $K$ such that $T$ belongs to ${\rm Bool}({\cal T}({\rm DTDA}))$
iff $T$ belongs to $K$-${\rm Bool}({\cal T}({\rm DTDA}))$?

## References

  * [1] M. Bojańczyk, Decidable properties of tree languages, PhD thesis, Warsaw University (2004).
  * [2] F. Gécseg and M. Steinby, Minimal ascending tree automata, Acta Cybern. 4(1) (1978) 37–44.
  * [3] F. Gécseg and M. Steinby, Tree Automata (Akadémiai Kiadó, Budapest, 1984).
  * [4] E. Jurvanen, The Boolean closure of DR-recognizable tree languages, Acta Cybern. 10(4) (1992) 255–272.
  * [5] E. Jurvanen, A. Potthoff and W. Thomas, Tree languages recognizable by regular frontier check, Developments in Language Theory, At the Crossroads of Mathematics, Computer Science and Biology, Turku, Finland, 12-15 July 1993, (World Scientific, Singapore, 1994), pp. 3–17.
  * [6] E. Jurvanen and M. Steinby, Fuzzy deterministic top-down tree automata, CoRR abs/1911.11529 (2019).
  * [7] P. Leupold and S. Maneth, Deciding top-down determinism of regular tree languages, Fundamentals of Computation Theory - 23rd International Symposium, FCT 2021, Athens, Greece, September 12-15, 2021, Proceedings, Lecture Notes in Computer Science 12867, (Springer, 2021), pp. 341–353.
  * [8] S. Maneth and H. Seidl, Checking in polynomial time whether or not a regular tree language is deterministic top-down, Inf. Process. Lett. 184 (2024) p. 106449.
  * [9] D. E. Muller, Infinite sequences and finite machines, Proceedings of the 4th IEEE Symposium on Switching Circuit Theory and Logical Design, (1963), pp. 3–16.
  * [10] M. O. Rabin, Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society 141 (July 1969) 1–35.
  * [11] W. Thomas, Languages, automata, and logic, Handbook of Formal Language Theory, eds. G. Rozenberg and A. Salomaa, III (Springer, 1997), pp. 389–455.
  * [12] J. Virágh, Deterministic ascending tree automata I., Acta Cybernet. 5 (1980) 33–42.


2.2] for further details on the computational aspects of these methods). Now,
let us consider the special case where $\Theta$ is the unit $\ell_{q}$-ball
for $q\in(2,\infty]$, i.e.,

$\Theta=\\{\boldsymbol{u}\in\mathbb{R}^{d}:\sum_{j=1}^{d}|\boldsymbol{u}_{j}|^{q}\leq
1\\},$

for $q\in(2,\infty)$, and

$\Theta=\\{\boldsymbol{u}\in\mathbb{R}^{d}:\max_{j\in[d]}|\boldsymbol{u}_{j}|\leq
1\\},$

for $q=\infty$. In [10, Lemma 11 and Theorem 5], the authors showed that any
$\mu$-self-concordant barrier on $\Theta$ should satisfy

$\mu\geq\texttt{A}\max\left(d^{\frac{1}{q}}\log(d)^{-\frac{q}{q-2}},d^{1-\frac{2}{q}}\right),$

where $\texttt{A}>0$ only depends on $q$. The lower bound indicates that for
the case of $q=\infty$, the $(d+1)$-self-concordant barrier proposed by [11,
22, 17] is optimal with respect to $\mu$ as a function of $d$. However,
constructing an optimal $\mu$-self-concordant barrier for any $\ell_{q}$-ball
for $q\in(2,\infty)$ remains an open problem.


# Hybrid DoF: Ray-Traced and Post-Processed Hybrid Depth of Field Effect for
Real-Time Rendering

Tan Yu Wei  National University of Singapore<EMAIL_ADDRESS>,  Nicholas Chua
National University of Singapore<EMAIL_ADDRESS>,  Nathan Biette
National University of Singapore<EMAIL_ADDRESS>and  Anand Bhojan
National University of Singapore<EMAIL_ADDRESS>
(2020)

###### Abstract.

Depth of Field (DoF) in games is usually achieved as a post-process effect by
blurring pixels in the sharp rasterized image based on the defined focus
plane. This paper describes a novel real-time DoF technique that uses ray
tracing with image filtering to achieve more accurate partial occlusion semi-
transparencies on edges of blurry foreground geometry. This hybrid rendering
technique leverages ray tracing hardware acceleration as well as spatio-
temporal reconstruction techniques to achieve interactive frame rates.

real-time, depth of field, ray tracing, post-processing, hybrid rendering,
games

††copyright: rightsretained††journalyear: 2020††conference: SIGGRAPH ’20
Posters; August 17, 2020; Virtual Event, USA††booktitle: Special Interest
Group on Computer Graphics and Interactive Techniques Conference Posters
(SIGGRAPH ’20 Posters), August 17, 2020††doi: 10.1145/3388770.3407426††isbn:
978-1-4503-7973-1/20/08††submissionid: pos_184††ccs: Computing methodologies
Rendering††ccs: Computing methodologies Ray tracing††ccs: Applied computing
Computer games

Figure 1. From left to right: original scene, adapted post-process (Jimenez,
2014) with foreground overblur, UE4 post-process (Abadie, 2018), hybrid (143
fps) and ray-traced DoF on The Modern Living Room (CC BY) with a GeForce RTX
2080 Ti

Close-up shot of foreground cushion whose left edge covers bottom right corner
of cushion in background

##  1\. Introduction

Under partial occlusion in Depth of Field (DoF), background information is
revealed through the semi-transparent silhouettes of blurry foreground
geometry. Partial occlusion is inaccurate with traditional post-processing as
the rasterized image does not store any information behind foreground objects.
We can query the scene for background intersections with ray tracing but at
poorer performance. Hence, we propose a DoF effect based on hybrid rendering,
which combines rasterization and ray tracing techniques for better visual
quality while maintaining interactive frame rates.

##  2\. Design

A G-Buffer is first produced in deferred shading with a sharp rasterized image
that undergoes post-process filtering adapted from Jimenez (2014). Selected
areas of the scene with higher rates of post-processing inaccuracy are then
chosen to undergo distributed ray tracing with spatio-temporal reconstruction.
The post-process and ray trace colours are finally composited together. We
build our technique on the thin lens model by Potmesil and Chakravarty (1982),
and define our scene such that points in front of the focus plane are in the
_near_ field and points behind are in the _far_ field.

###  2.1. Ray Trace

We shoot a variable number of rays into the scene through an adaptive ray
mask. Employing a selective rendering approach like in adaptive frameless
rendering, we aim to shoot more rays at edges to create clean semi-
transparencies but less at regions with fewer details such as plain surfaces.
Like Canny Edge Detection, we apply a Gaussian filter on the G-Buffer first to
reduce noise and jaggies along diagonal edges. The filtered G-Buffer then
passes through a Sobel kernel to approximate the gradient associated with each
pixel based on the differences in surface normal and depth with its
surrounding pixels, detecting geometry edges for the ray mask. Accounting for
temporal variation to reduce noise, we also shoot more rays at areas of high
variance in luminance, including newly ray-traced regions. Hence, the ray mask
is complemented with a temporally-accumulated variance estimate (Schied et
al., 2017) from the ray trace output of previous frames.

We then shoot rays, taking multiple samples in a circle to produce random ray
origins within the lens’ area. At the edge of an out-of-focus foreground
object, rays originating from the lens will either hit the object or objects
behind it, yielding a semi-transparent silhouette. We sort the hits into the
_near_ and _far_ fields. However, to have a smooth colour transition, we split
the contribution of pixel colour to each layer based on its Z-distance from
the separating focus plane. A hit ratio is also stored, which is the number of
rays contributing to the _near_ colour divided by the total rays shot.

###  2.2. Reconstruction

To increase our sample count, we temporally-accumulate _near_ and _far_ ray
trace colours over time and use an exponential moving average to blend between
history and current frames like in TAA. However, to account for movement, we
leverage per-pixel depth and motion information for reprojection like Lehtinen
et al. (2011).

As such, we use screen space motion vectors to reproject _near_ pixels. As for
the _far_ field, we require an approximation of the _far_ world position of
our pixel. We first attempt to compute the average world position of our pixel
from _far_ ray trace hits. Under low ray counts, in the event that there is no
_far_ hit, we obtain the average _far_ world position of neighbouring pixels
instead. Then, we use this world position to calculate the previous screen
space position of the pixel, approximating reprojection for occluded objects
appearing within semi-transparent regions of foreground geometry. However, to
prevent the ghosting (or smearing) of these regions, we use the latest hit
ratio to compose the _near_ and _far_ colours during motion, but normalize the
final colour based on the accumulated hit ratio since reprojection is
different for the _near_ and _far_ fields. Otherwise, we risk having varying
colour intensities in our merged result.

We also blend the new average _near_ and _far_ Circle of Confusion (CoC) sizes
based on the accumulated hit ratio, so as to get an approximate CoC size for
the current frame to scale our circular gathering kernel and determine the
level-of-detail for sampling in spatial reconstruction. Similar to our post-
processing approach, we gather the colour contributions of neighbouring
pixels, and samples with CoC radius smaller than their distance to the pixel
are rejected. Finally, the gathered colour is weighted based on clamped
variance estimates to avoid over-blurring in converged regions.

###  2.3. Composite

For the final image, we apply the ray trace, post-process and sharp rasterized
colours onto pixels based on their Z-values in relation to the focus zone,
where the CoC size of pixels is less than $\sqrt{2}$ and hence the unblurred
rasterized colour is applied. Outside the focus zone, for _near_ objects in
general, we apply the ray trace colour to form accurate semi-transparent
silhouettes. However, for bright specular bokeh shapes, we favour the post-
process over the ray trace colour based on the intensity of the specular
component of the post-process colour, so as to minimize noise from the ray
trace.

For _far_ geometry out of the focus zone, we adaptively blend the ray trace
and post-process colours using the hit ratio. At high hit ratios, we favour
the post-process colour as fewer rays hit the _far_ field. On the other hand,
low hit ratios indicate that the number of hits in the _far_ field is
comparable to that of the _near_ field, so more ray trace colour is used.
However, there are also fewer _near_ hits closer to the edges of the ray mask,
favouring the ray trace colour. Hence, using our hit ratio as-is causes blur
discontinuities and tiling artifacts from the mask. To minimize them while
trying to retain the ray-traced semi-transparencies, we only blend at hit
ratios below a certain value for a smooth transition between the ray trace and
post-process colours around the edges of the ray mask.

##  3\. Discussion

Partial occlusion is more accurate for hybrid DoF as background details which
would otherwise be hidden are uncovered in the silhouettes of blurry
foreground objects with ray tracing. In contrast, many post-process approaches
only perform a local approximation of the background with neighbouring pixels
or grow blur out of the silhouette of foreground objects, reusing foreground
information to avoid reconstructing the missing background (Jimenez, 2014).

In future, we plan to scale the ray mask resolution based on the maximum CoC
to prevent tiling artifacts and estimate per-pixel blend factors (Schied et
al., 2018) to minimize ghosting. We also intend to extend our approach to
support alternative bokeh shapes and not just circular ones of uniform
intensities, by varying the shape of our sampling kernel and the relative
weight of its samples based on the desired silhouette of the camera aperture
and spherical aberration quality of its lens respectively.

###### Acknowledgements.

This work is supported by the Singapore Ministry of Education Academic
Research grant T1 251RES1812, “Dynamic Hybrid Real-time Rendering with
Hardware Accelerated Ray-tracing and Rasterization for Interactive
Applications”.

## References

  * (1)
  * Abadie (2018) Guillaume Abadie. 2018\.  Advances in Real-Time Rendering in Games: A Life of a Bokeh. In _ACM SIGGRAPH 2018 Courses_ (Vancouver, British Columbia, Canada) _(SIGGRAPH ’18)_. Association for Computing Machinery, New York, NY, USA, Article 20, 1 pages.  https://doi.org/10.1145/3214834.3264541
  * Jimenez (2014) Jorge Jimenez. 2014\.  Advances in Real-Time Rendering in Games, Part I: Next Generation Post Processing in Call of Duty: Advanced Warfare.  http://advances.realtimerendering.com/s2014/#_NEXT_GENERATION_POST
  * Lehtinen et al. (2011) Jaakko Lehtinen, Timo Aila, Jiawen Chen, Samuli Laine, and Frédo Durand. 2011.  Temporal Light Field Reconstruction for Rendering Distribution Effects.  _ACM Trans. Graph._ 30, 4, Article 55 (July 2011), 12 pages.  https://doi.org/10.1145/2010324.1964950
  * Potmesil and Chakravarty (1982) Michael Potmesil and Indranil Chakravarty. 1982.  Synthetic Image Generation with a Lens and Aperture Camera Model.  _ACM Trans. Graph._ 1, 2 (April 1982), 85–108.  https://doi.org/10.1145/357299.357300
  * Schied et al. (2017) Christoph Schied, Anton Kaplanyan, Chris Wyman, Anjul Patney, Chakravarty R. Alla Chaitanya, John Burgess, Shiqiu Liu, Carsten Dachsbacher, Aaron Lefohn, and Marco Salvi. 2017.  Spatiotemporal Variance-guided Filtering: Real-time Reconstruction for Path-traced Global Illumination. In _Proceedings of High Performance Graphics_ (Los Angeles, California) _(HPG ’17)_. ACM, New York, NY, USA, Article 2, 12 pages.  https://doi.org/10.1145/3105762.3105770
  * Schied et al. (2018) Christoph Schied, Christoph Peters, and Carsten Dachsbacher. 2018.  Gradient Estimation for Real-Time Adaptive Temporal Filtering.  _Proc. ACM Comput. Graph. Interact. Tech._ 1, 2, Article 24 (Aug. 2018), 16 pages.  https://doi.org/10.1145/3233301