A connection between the Cantor–Bendixson derivative and the well-founded semantics of finite logic programs

Results of Schlipf (J Comput Syst Sci 51:64?C86, 1995) and Fitting (Theor Comput Sci 278:25?C51, 2001) show that the well-founded semantics of a finite predicate logic program can be quite complex. In this paper, we show that there is a close connection between the construction of the perfect kernel of a $\Pi^0_1$ class via the iteration of the Cantor?CBendixson derivative through the ordinals and the construction of the well-founded semantics for finite predicate logic programs via Van Gelder??s alternating fixpoint construction. This connection allows us to transfer known complexity results for the perfect kernel of $\Pi^0_1$ classes to give new complexity results for various questions about the well-founded semantics ${\mathit{wfs}}(P)$ of a finite predicate logic program P.     

On the robustness and optimality of algebraic multilevel methods for reaction–diffusion type problems

This paper is on preconditioners for reaction–diffusion problems that are both, uniform with respect to the reaction–diffusion coefficients, and optimal in terms of computational complexity. The considered preconditioners belong to the class of so-called algebraic multilevel iteration (AMLI) methods, which are based on a multilevel block factorization and polynomial stabilization. The main focus of this work is on the construction and on the analysis of a hierarchical splitting of the conforming finite element space of piecewise linear functions that allows to meet the optimality conditions for the related AMLI preconditioner in case of second-order elliptic problems with non-vanishing zero-order term. The finite element method (FEM) then leads to a system of linear equations with a system matrix that is a weighted sum of stiffness and mass matrices. Bounds for the constant \(\gamma \) in the strengthened Cauchy–Bunyakowski–Schwarz inequality are computed for both mass and stiffness matrices in case of a general \(m\) -refinement. Moreover, an additive preconditioner is presented for the pivot blocks that arise in the course of the multilevel block factorization. Its optimality is proven for the case \(m=3\) . Together with the estimates for \(\gamma \) this shows that the construction of a uniformly convergent AMLI method with optimal complexity is possible (for \(m \ge 3\) ). Finally, we discuss the practical application of this preconditioning technique in the context of time-periodic parabolic optimal control problems.     

On the space–time of optimal, approximate and streaming algorithms for synopsis construction problems

Synopses construction algorithms have been found to be of interest in query optimization, approximate query answering and mining, and over the last few years several good synopsis construction algorithms have been proposed. These algorithms have mostly focused on the running time of the synopsis construction vis-a-vis the synopsis quality. However the space complexity of synopsis construction algorithms has not been investigated as thoroughly. Many of the optimum synopsis construction algorithms are expensive in space. For some of these algorithms the space required to construct the synopsis is significantly larger than the space required to store the input. These algorithms rely on the fact that they require a smaller “working space” and most of the data can be resident on disc. The large space complexity of synopsis construction algorithms is a handicap in several scenarios. In the case of streaming algorithms, space is a fundamental constraint. In case of offline optimal or approximate algorithms, a better space complexity often makes these algorithms much more attractive by allowing them to run in main memory and not use disc, or alternately allows us to scale to significantly larger problems without running out of space. In this paper, we propose a simple and general technique that reduces space complexity of synopsis construction algorithms. As a consequence we show that the notion of “working space” proposed in these contexts is redundant. This technique can be easily applied to many existing algorithms for synopsis construction problems. We demonstrate the performance benefits of our proposal through experiments on real-life and synthetic data. We believe that our algorithm also generalizes to a broader range of dynamic programs beyond synopsis construction. Sudipto Guha’s research supported in part by an Alfred P. Sloan Research Fellowship and by NSF Awards CCF-0430376, CCF-0644119.A preliminary version of the paper appeared as “Space efficiency in synopsis construction algorithms”, VLDB Conference 2005, Trondheim, [19].     

On Convergence of the Arrow–Hurwicz Method for Saddle Point Problems

Journal of Mathematical Imaging and Vision - The Arrow–Hurwicz method is an inexact version of the Uzawa method; it has been widely applied to solve various saddle point problems in different...     

On a collocation B-spline method for the solution of the Navier–Stokes equations

A novel B-spline collocation method for the solution of the incompressible Navier–Stokes equations is presented. The discretization employs B-splines of maximum continuity, yielding schemes with high-resolution power. The Navier–Stokes equations are solved by using a fractional step method, where the projection step is considered as a Div–Grad problem, so that no pressure boundary conditions need to be prescribed. Pressure oscillations are prevented by introducing compatible B-spline bases for the velocity and pressure, yielding efficient schemes of arbitrary order of accuracy. The method is applied to two-dimensional benchmark flows, and mass lumping techniques for cost-effective computation of unsteady problems are discussed.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

On the combination of logical and probabilistic models for?information analysis

Formal logical tools are able to provide some amount of reasoning support for information analysis, but are unable to represent uncertainty. Bayesian network tools represent probabilistic and causal information, but in the worst case scale as poorly as some formal logical systems and require specialized expertise to use effectively. We describe a framework for systems that incorporate the advantages of both Bayesian and logical systems. We define a formalism for the conversion of automatically generated natural deduction proof trees into Bayesian networks. We then demonstrate that the merging of such networks with domain-specific causal models forms a consistent Bayesian network with correct values for the formulas derived in the proof. In particular, we show that hard evidential updates in which the premises of a proof are found to be true force the conclusions of the proof to be true with probability one, regardless of any dependencies and prior probability values assumed for the causal model. We provide several examples that demonstrate the generality of the natural deduction system by using inference schemes not supportable directly in Horn clause logic. We compare our approach to other ones, including some that use non-standard logics.     

On the global existence of dissipative solutions for the modified coupled Camassa–Holm system

This paper investigates the dynamic behavior of the modified coupled two-component Camassa–Holm dynamic system arisen from shallow water waves moving. By using a skillfully defined characteristic and a set of newly introduced variables, the original system is converted into a Lagrangian semilinear one in which the associated energy is introduced as an additional variable so as to obtain a well-posed initial-value problem, facilitating the study on the behavior of wave breaking. It is established that the solutions of the system continue as global dissipative solutions after wave breaking, which presents an interesting and useful result for better understanding the inevitable phenomenon before and after wave breaking.     

On the size of Boyer–Moore automata

In this work we study the size of Boyer–Moore automata introduced in Knuth, Morris & Pratt’s famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer–Moore automata, and find one particular case which we conjecture, generates automata of size Ω(m⁶)$\Omega \left(m^6\right)$. Further experimental results suggest that the maximal size could be a polynomial of O(m⁷)$O\left(m^7\right)$, or even an exponential O(2^0.4m)$O\left(2^{0.4m}\right)$, where m$m$ is the length of the pattern.     

On the computation of Bernstein–Sato ideals

In this paper we compare the approach of Briançon and Maisonobe for computing Bernstein–Sato ideals—based on computations in a Poincaré–Birkhoff–Witt algebra—with the readily available method of Oaku and Takayama. We show that it can deal with interesting examples that have proved intractable so far.     

On a Petrov–Galerkin method for the electrical and thermal behaviour of semiconductor devices in two dimensions

We consider the equations governing the electrical and thermal behaviour of a semiconductor device in two dimensions. A non-standard Petrov-Galerkin method is used to obtain a discretisation of the equations for stationary problems. The resulting scheme is a generalization to the two-dimensional case and to the full set of equations of the well-known Scharfetter-Gummel scheme, which is the most successful discretisation for one-dimensional problems. The dependent variables used are the carrier densities, the electrostatic potential and the absolute temperature.     

On the usefulness of off-the-shelf computer peripherals for people with Parkinson’s Disease

People who suffer from Parkinson’s Disease face many challenges using computers, and mice are particularly problematic input devices. This article describes usability tests of standard peripherals for use by people with Parkinson’s Disease in order to identify optimal combinations with respect to the needs of this user group. The results are used to determine their effect upon inertia, muscle stiffness, tremor, pain, strain and coordination and show that widely available equipment could significantly improve mouse pointer control for many users. The results reflect the diversity of challenges experienced by computer users with Parkinson’s Disease, and also illustrate how projector-based technology may improve computer interaction without risking strain injuries.     

On the Numerical Controllability of the Two-Dimensional Heat,Stokes and Navier–Stokes Equations

The aim of this work is to present some strategies to solve numerically controllability problems for the two-dimensional heat equation, the Stokes equations and the Navier–Stokes equations with Dirichlet boundary conditions. The main idea is to adapt the Fursikov–Imanuvilov formulation, see Fursikov and Imanuvilov (Controllability of Evolutions Equations, Lectures Notes Series, vol 34, Seoul National University, 1996); this approach has been followed recently for the one-dimensional heat equation by the first two authors. More precisely, we minimize over the class of admissible null controls a functional that involves weighted integrals of the state and the control, with weights that blow up near the final time. The associated optimality conditions can be viewed as a differential system in the three variables \(x_1\), \(x_2\) and t that is second-order in time and fourth-order in space, completed with appropriate boundary conditions. We present several mixed formulations of the problems and, then, associated mixed finite element Lagrangian approximations that are relatively easy to handle. Finally, we exhibit some numerical experiments.     

On the adjoint-consistent formulation of interface conditions in goal-oriented error estimation and adaptivity for fluid–structure interaction

The numerical solution of fluid–structure-interaction problems poses a paradox in that most of the computational resources are consumed by the subsystem of least practical interest, viz., the fluid. Goal-oriented adaptive discretization methods provide a paradigm to bypass this paradox. Based on the solution of a dual problem, the contribution of local residuals to the error in a specific goal functional is estimated, and only the regions that yield a dominant contribution are refined. In the present work, we address a fundamental complication in the application of goal-oriented adaptivity to fluid–structure-interaction problems, namely, that the treatment of the interface conditions has nontrivial consequences for the properties of the dual problem. In the context of a linearized model problem, we consider two equivalent discretizations differing only on the formulation of the interface coupling terms. By means of an adjoint consistency analysis, we show that only one of these discretizations is adjoint consistent. Numerical experiments convey that the two discretizations behave very differently for the dual problem, and that the adjoint-consistent discretization yields more reliable error estimates. Based on the adjoint-consistent discretization, we finally present some h- and hp-adaptive results, confirming that tremendous savings in computational cost can be realized through the use of goal-oriented refinement strategies. The numerical experiments illustrate that the goal-oriented approach effectively equilibrates the error contributions of the fluid and structure subsystems, which is imperative for efficiently resolving the coupled fluid–structure-interaction problem, and which cannot be accomplished by uniform or residual-based refinement strategies.     

On the stability and convergence of self-tuning control–virtual equivalent system approach

This article presents a unified understanding and judgement of the stability and convergence of a general self-tuning control (STC) system, which consists of arbitrary control strategy, arbitrary parameter estimation algorithm and a deterministic/stochastic linear time-invariant (LTI) plant. The necessary conditions required for the global stability and convergence of a general STC system are relaxed, i.e. the convergence of parameter estimates is removed for both deterministic and stochastic STC schemes. To reach this goal, ‘virtual equivalent system (VES)’ concept and methodology is adopted. With the help of VES, the original nonlinear dominant (nonlinear in structure) problem is converted to a linear dominant (linear in structure) problem. The results developed in this article show that STC systems are stable and convergent for the abundance of control strategies and parameter estimation algorithms, which will provide great flexibility in the applications of STC.     

Operational semantics of a domain specific language for real time musician–computer interaction

With the advent and availability of powerful personal computing, the computer music research and industry have been focusing on real-time musical interactions between musicians and computers; delegating human-like actions to computers who interact with a musical environment. One common use-case of this kind is Automatic Accompaniment where the system is comprised of a real-time machine listening system that in reaction to recognition of events in a score from a human performer, launches necessary actions for the accompaniment section. While the real-time detection of score events out of live musicians’ performance has been widely addressed in the literature, score accompaniment (or the reactive part of the process) has been rarely discussed. This paper deals with this missing component in the literature from a formal language perspective. We show how language considerations would enable better authoring of time and interaction during programming/composing and how it addresses critical aspects of a musical performance (such as errors) in real-time. We sketch the real-time features required by automatic musical accompaniment seen as a reactive system. We formalize the timing strategies for musical events taking into account the various temporal scales used in music. Various strategies for the handling of synchronization constraints and the handling of errors are presented. We give a formal semantics to model the possible behaviors of the system in terms of Parametric Timed Automata.     

On the applicability of capability models for small software organizations: does the use of standard processes lead to a better achievement of business goals?

The ISO/IEC 15504 standard implies that the use of its level-based capability model for software process development leads to a better business performance. At capability level 3, this would mean that there is not only a positive correlation but also a causal relation from the use of standard processes to better achievement of business goals. In this paper, we make this claim explicit and challenge it with a counterargument in the context of small software organizations. We argue that in most part, the way the software is designed is what determines the business success in software development, and when application domains are complex socio-technical systems, relying on a standard process instead of human expertise not only fails to answer the promise of process stability but also presents business risks related to poor design, a loss of diversity, and reduced adaptability. With reasons to believe that the standard’s claim is weak in this context, we come up with alternative explanations for why some small software organizations nevertheless use standard processes. Through these hypotheses, we argue that the reasons are not necessarily process-related. In closing, we suggest further studies on how the standard’s notion of process capability and business goals relate to each other when the application domain is not just complicated but complex.