We study the asymptotic behavior of $\lambda v_{\lambda }$ as $\lambda \to 0^{+}$, where $v_{\lambda }$ is the viscosity solution of the following Hamilton-Jacobi-Isaacs equation (infinite horizon case) $$\lambda v_{\lambda }+H(x,D{v}_{\lambda })=0,$$ with $$H(x,p):=\underset{b\in B}{min}\underset{a\in A}{max}\{-f(x,a,b)·p-l(x,a,b)\}.$$ We discuss the cases in which the state of the system is required to stay in an -dimensional torus, called periodic boundary conditions, or in the closure of a bounded connected domain $\Omega \subset {}^n$ with sufficiently smooth boundary. As far as the latter is concerned, we treat both the case of the Neumann boundary conditions (reflection...

The first-value operator assigns to any sequence of partial functions of the same type a new such function. Its domain is the union of the domains of the sequence functions, and its value at any point is just the value of the first function in the sequence which is defined at that point. In this paper, the first-value operator is applied to establish hierarchies of classes of functions under various settings. For effective sequences of computable discrete functions, we obtain a hierarchy...

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W\left[P\right]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W\left[P\right]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

The paradigm of type-based termination is explored for functional programming with recursive data types. The article introduces ${\Lambda }_{\mu }^{+}$, a lambda-calculus with recursion, inductive types, subtyping and bounded quantification. Decorated type variables representing approximations of inductive types are used to track the size of function arguments and return values. The system is shown to be type safe and strongly normalizing. The main novelty is a bidirectional type checking algorithm...

In this paper, we consider a Borel measurable function on the space of $m\times n$ matrices $f:M^{m\times n}\to \overline{ℝ}$ taking the value $+\infty$, such that its rank-one-convex envelope $Rf$ is finite and satisfies for some fixed $p>1$: $$-c_0\le Rf\left(F\right)\le {c(1+\parallel F\parallel }^p)\text{for}\text{all}F\in M^{m\times n},$$ where $c,c_0>0$. Let $Ø$ be a given regular bounded open domain of ${ℝ}^n$. We define on $W^{1,p}(Ø;{ℝ}^m)$ the functional $$I\left(u\right)={\int }_{Ø}f\left(\nabla u\left(x\right)\right)dx.$$ Then, under some technical restrictions on $f$, we show that the relaxed functional $\overline{I}$ for the weak topology of $W^{1,p}(Ø;{ℝ}^m)$ has the integral representation: $$\overline{I}\left(u\right)={\int }_{Ø}Q\left[Rf\right]\left(\nabla u\left(x\right)\right)dx,$$ where for a given function $g$, $Qg$ denotes...

The complexity of computing, via threshold circuits, the and of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ and ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$, respectively, for short. We prove that: (i) For $k\ge 2$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$.newline (ii) For : ${\mathrm{𝖨𝖬𝖯}}_{\mathsf{2}}$ belongs to ${\mathrm{TC}}^0$ while, for $k\ge 3$, ${\mathrm{𝖨𝖬𝖯}}_{𝗄}$ does not belong to ${\mathrm{TC}}^0$, unless ${\mathrm{TC}}^0={\mathrm{NC}}^1$. (iii) For any , ${\mathrm{𝖬𝖯𝖮𝖶}}_{𝗄}$ belongs to ${\mathrm{TC}}^0$.