Checking the satisfiability of formulas represented in disjunctive normal form in the language <Emphasis Type="Italic">L</Emphasis>. II

This paper concentrates on issues of implementation of the method proposed for checking the consistency of formulae of the language L and described in the first part of this work. Upper-bound estimates of time complexity of the corresponding algorithms are obtained. Part I of this article is published in No. 4 (2005). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 11–19, November–December 2005.     

Automatic analysis of DMA races using model checking and <Emphasis Type="Italic">k</Emphasis>-induction

Modern multicore processors, such as the Cell Broadband Engine, achieve high performance by equipping accelerator cores with small “scratch-pad” memories. The price for increased performance is higher programming complexity – the programmer must manually orchestrate data movement using direct memory access (DMA) operations. Programming using asynchronous DMA operations is error-prone, and DMA races can lead to nondeterministic bugs which are hard to reproduce and fix. We present a method for DMA race analysis in C programs. Our method works by automatically instrumenting a program with assertions modeling the semantics of a memory flow controller. The instrumented program can then be analyzed using state-of-the-art software model checkers. We show that bounded model checking is effective for detecting DMA races in buggy programs. To enable automatic verification of the correctness of instrumented programs, we present a new formulation of k-induction geared towards software, as a proof rule operating on loops. Our techniques are implemented as a tool, Scratch, which we apply to a large set of programs supplied with the IBM Cell SDK, in which we discover a previously unknown bug. Our experimental results indicate that our k-induction method performs extremely well on this problem class. To our knowledge, this marks both the first application of k-induction to software verification, and the first example of software model checking in the context of heterogeneous multicore processors.     

Categorical properties of solvability for one class of minimization problems<Superscript>1</Superscript>

A lower semicontinuous functional disturbed by a Minkowski functional of a closed bounded convex neighborhood of zero possessing the Kadets–Klee property is minimized on a closed subset X of a reflexive Banach space E. It is proved that the set of parameters for which the problem has a solution contains a G_δ-subset dense in E \ X. It is shown that the reflexivity condition and the condition of the Kadets–Klee property of the neighborhood cannot be weakened. The application to optimization problems for linear systems with vector performance criteria is considered.     

Coherence checking and propagation of lower probability bounds

 In this paper we use imprecise probabilities, based on a concept of generalized coherence (g-coherence), for the management of uncertain knowledge and vague information. We face the problem of reducing the computational difficulties in g-coherence checking and propagation of lower conditional probability bounds. We examine a procedure, based on linear systems with a reduced number of unknowns, for the checking of g-coherence. We propose an iterative algorithm to determine the reduced linear systems. Based on the same ideas, we give an algorithm for the propagation of lower probability bounds. We also give some theoretical results that allow, by suitably modifying our algorithms, the g-coherence checking and propagation by working with a reduced set of variables and/or with a reduced set of constraints. Finally, we apply our algorithms to some examples. RID="*" ID="*" This paper is a revised and substantially extended version of a previous paper by the same authors, appeared in the Proc. of the 5th Workshop on Uncertainty Processing (WUPES'2000), Jindřichu̇v Hradec, Czech Republic, June 21–24, 1–13, 2000.     

Reverse Shooting Made <Emphasis Type="Italic">Easy</Emphasis>: Automating the Search for the Global Nonlinear Saddle Path

We present the blueprints for a set of innovative reverse shooting algorithms that trap the global saddle path in systems with 2–4 state variables. The solution procedure is built around a new distance mapping and refined simplex algorithms. Since the algorithms are completely reliable and always work in the same way, we have been able to develop canned programs that solve for the global nonlinear saddle path in any model with 2–4 state variables. The programs are written in the spirit of plug and play: the user types in the equations of the model and then waits for the solution.     

<Emphasis Type="Italic">R</Emphasis>-functions in mathematical modeling of geometric objects with symmetry

Normalized equations for regular n_o-gons translated n_d times in a regular n_b-gon are set up based on coordinate transformations that allow translating geometric objects on segments. Such approaches are especially important in solving automation problems in solid modeling, geometric design, and boundary-value problems of mathematical physics. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 75–83, November–December 2008.     

Separable resolution method for checking the satisfiability of formulas in the languageL

Conclusion This paper offers an effective resolution method for checking the satisfiability of a collection of disjuncts in the languageL. The method permits one to substantially reduce the number of generated resolvents in comparison with the method ofR-resolution. One more factor ensuring the efficiency of the method is a significant reduction in the number of disjunct pairs checked for the possibility of resolving them. As for the number of generated disjuncts, its greatest reduction is obtained in the case of the use of the disjunct-set partition corresponding to the limiting system of predicate-symbol subsets given by symbol ordering. It is possible to interpret the result obtained for this case as proof of the completeness of the strategy combining an ordering of predicate symbols andR-resolution. It is necessary to note that to different orderings of predicate symbols correspond different partitions of the disjunct set giving, in turn, different numbers of generated disjuncts in the process ofSp-completion. Nevertheless, the methods described in Sec. 2, which use partition of the disjunct set into two classes, are of independent importance. As has already been said, completion of a disjunct set is used for solution of a number of problems during the design of a procedural automaton specification. For example, in the case of checking the consistency of two interacting automata [5] based on completion of a disjunct set, there exists a natural partition of the predicate symbols into input and output symbols, to which corresponds the partition of the disjunct set into subsets specifying the interacting automata. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 13–20, November–December, 1998.     

<Emphasis Type="Italic">G</Emphasis>*-Convergence of Nonlinear Operators in the Theory of Homogenization of Control Objects

To study problems of homogenization of one class of control objects described by nonlinear operator equations, the concept of G*-convergence of nonlinear operators is introduced. The sufficient conditions of identifiability of homogenized objects are obtained. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 42–65, September–October 2005.     

Extension of <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis> log <Emphasis Type="Italic">n</Emphasis>) Filtering Algorithms for the Unary Resource Constraint to Optional Activities

Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. These algorithms use a special data structures Θ-tree and Θ-Λ-tree. These data structures are especially designed for “what-if” reasoning about a set of activities so we also propose to use them for handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.     

Approximation of sets of superwords by <Emphasis Type="Italic">L</Emphasis>-language formulas

L is a language for specifying properties of reactive systems. Such properties are considered as sets of words over the alphabet defined by a specification. Properties that correspond to complements of such sets are not expressible in the language L. An approach is proposed to constructing formulas of the language L that specify approximations of complements of sets defined in L. These investigations were partially supported by INTAS grant 05-1000008-8144. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 18–26, November–December 2007.     

On the Long-Time <Emphasis Type="Italic">H</Emphasis><Superscript>2</Superscript>-Stability of the Implicit Euler Scheme for the 2D Magnetohydrodynamics Equations

Pursuing our work in Tone (Asymptot. Analysis 51:231–245, 2007) and Tone and Wirosoetisno (SIAM J. Number. Analysis 44:29–40, 2006), we consider in this article the two-dimensional magnetohydrodynamics equations, we discretize these equations in time using the implicit Euler scheme and with the aid of the classical and uniform discrete Gronwall lemma, we prove that the scheme is H ²-uniformly stable in time.     

Managing the verification trajectory

In this paper we take a closer look at the automated analysis of designs, in particular of verification by model checking. Model checking tools are increasingly being used for the verification of real-life systems in an industrial context. In addition to ongoing research aimed at curbing the complexity of dealing with the inherent state space explosion problem – which allows us to apply these techniques to ever larger systems – attention must now also be paid to the methodology of model checking, to decide how to use these techniques to their best advantage. Model checking “in the large” causes a substantial proliferation of interrelated models and model checking sessions that must be carefully managed in order to control the overall verification process. We show that in order to do this well both notational and tool support are required. We discuss the use of software configuration management techniques and tools to manage and control the verification trajectory. We present Xspin/Project, an extension to Xspin, which automatically controls and manages the validation trajectory when using the model checker Spin. Published online: 18 June 2002     

Number of cyclically irreducible words in the alphabet of a free group of finite rank

It is shown that a formula that was independently obtained earlier for the number of cyclically irreducible words of length n in a symmetric alphabet of a finitely generated free group of rank k and the Whitney formula for a chromatic polynomial of a simple nonself-intersecting cycle of length n with a variable λ are mutually deducible from one another when λ = 2k. The necessary bijections differ for even and odd values of n. To the memory of William T. Tutte (05.14.1917–05.02.2002) __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 39–48, July–August 2007.     

<Emphasis Type="Italic">Ontologie(n)</Emphasis>

Ontologie ist ein überlieferter Begriff aus der Philosophie und steht dort für die Lehre vom Sein – genauer: von den M?glichkeiten und Bedingungen des Seienden –, ist also eng verwandt mit der Erkenntnistheorie, die sich mit den M?glichkeiten und Grenzen menschlichen Wahrnehmens und Erkennens auseinander setzt. Vorschl?ge an Prof. Dr. Frank <puppe@informatik.uni-wuerzburg.de> oder Dieter Steinbauer <dieter.steinbauer@schufa.de> Alle „Aktuellen Schlagw?rter” seit 1988 finden Sie unter www.ai-wuerzburg.de/as     

Mathematical modeling of mass transfer in symmetric heterogeneous and nanoporous media with a system of <Emphasis Type="Italic">n</Emphasis>-interface interactions

An exact analytical solution is obtained to describe mass transfer in symmetric heterogeneous and nanoporous media with a system of n-interface interactions. The Laplace integral transform and Cauchy fundamental functions are used. A solvability theorem is proved. New recurrence algorithms and computational procedures are developed to form influence matrices, which are due to heterogeneities and n-interface interactions. __________ Translated from Kibernetika I Sistemnyi Analiz, No. 1, pp. 114–134, January–February 2007.     

A new approach to the decomposition of Boolean functions by the method of <Emphasis Type="Italic">q</Emphasis>-partitions. III. Joint decomposition of a function system

The paper considers the set-theoretical approach to the joint decomposition of systems of Boolean functions of variables specified in different representation forms. The approach is based on the method of q-partitions of conjuncterms and concept of decomposition clones. Theorems on joint decomposition of a system of full and partial functions are formulated. The approach is illustrated by examples. Parts I and II of this article are published in No. 5 (2001) and No. 1 (2002). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 39–58, March–April 2007.     

Orientation contrast sensitive cells in primate V1 <Emphasis Type="Italic">a computational model</Emphasis>

Many cells in the primary visual cortex respond differently when a stimulus is placed outside their classical receptive field (CRF) compared to the stimulus within the CRF alone, permitting integration of information at early levels in the visual processing stream that may play a key role in intermediate-level visual tasks, such a perceptual pop-out [Knierim JJ, van Essen DC (1992) J Neurophysiol 67(5):961–980; Nothdurft HC, Gallant JL, Essen DCV (1999) Visual Neurosci 16:15–34], contextual modulation [Levitt JB, Lund JS (1997) Nature 387:73–76; Das A, Gilbert CD (1999) Nature 399:655–661; Dragoi V, Sur M (2000) J Neurophysiol 83:1019–1030], and junction detection [Sillito AM, Grieve KL, Jones HE, Cudiero J, Davis J (1995) Nature 378:492–496; Das A, Gilbert CD (1999) Nature 399:655–661; Jones HE, Wang W, Sillito AM (2002) J Neurophysiol 88:2797–2808]. In this article, we construct a computational model in programming environment TiViPE [Lourens T (2004) TiViPE—Tino’s visual programming environment. In: The 28th Annual International Computer Software & Applications Conference, IEEE COMPSAC 2004, pp 10–15] of orientation contrast type of cells and demonstrate that the model closely resembles the functional behavior of the neuronal responses of non-orientation (within the CRF) sensitive 4Cβ cells [Jones HE, Wang W, Sillito AM (2002) J Neurophysiol 88:2797–2808], and give an explanation of the indirect information flow in V1 that explains the behavior of orientation contrast sensitivity. The computational model of orientation contrast cells demonstrates excitatory responses at edges near junctions that might facilitate junction detection, but the model does not reveal perceptual pop-out.     

Corepresentation of a sylow <Emphasis Type="Italic">p</Emphasis>-subgroup of a group <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The corepresentation of a Sylow p-subgroup of a symmetric group in the form of generating relations is investigated, and a Sylow subgroup of a group , i.e., an n-fold wreath product of regular cyclic groups of prime order, that is isomorphic to the group of automorphisms of a spherically homogeneous root tree is also studied. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 27–41, January–February 2009.     

An a posteriori error estimate and a comparison theorem for the nonconforming <Emphasis Type="Italic">P</Emphasis><Subscript>1</Subscript> element

A posteriori error estimates for the nonconforming P ₁ element are easily determined by the hypercircle method via Marini’s observation on the relation to the mixed method of Raviart–Thomas. Another tool is Ainsworth’s application of the hypercircle method to mixed methods. The relation on the finite element solutions is also extended to an a priori relation of the errors, and the errors of four different finite element methods can be compared.      

Generalization of Linear Morphisms on <Emphasis Type="Italic">N</Emphasis> in Topoi

The definition of linear morphisms is generalized to the natural number object. Properties of such morphisms are investigated. The necessary and sufficient condition of monocity of a linear morphism of an arbitrary topos is formulated. Linear monomorphisms are demonstrated to be split. Two proofs of complementarity and, accordingly, decidability of linear monomorphisms are proposed. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 66–72, September–October 2005.