Finding tree patterns consistent with positive and negative examples using queries

This paper is concerned with the problem of finding a hypothesis in consistent with given positive and negative examples. The hypothesis class consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages. Especially, we consider the problem from the point of view of the consistency problem for . The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete for many hypothesis spaces. In this paper, the problem for the class is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result, we have that the consistency problem for is solved in polynomial time using membership queries. This revised version was published online in June 2006 with corrections to the Cover Date.     

Classification using information

Let be a set of functions. A classifier for is a way of telling, given a function f, if f is in . We will define this notion formally. We will then modify our definition in three ways: (1) allow the classifier to ask questions to an oracle A (thus increasing the classifiers computational power), (2) allow the classifier to ask questions about f (thus increasing the classifiers information access), and (3) restrict the number of times the classifier can change its mind (thus decreasing the classifiers information access). By varying these parameters we will gain a better understanding of the contrast between computational power and informational access. We have determined exactly (1) which sets are classifiable (theorem 3.6), (2) which sets are classifiable with queries to some oracle (theorem 3.2), (3) which sets are classifiable with queries to some oracle and queries about f (theorem 5.2), and (4) which sets are classifiable with queries to some oracle, queries about f and a bounded number of mindchanges (theorem 5.2). The last two items involve the Borel hierarchy. This revised version was published online in June 2006 with corrections to the Cover Date.     

A semantically complete extension sequence of the system $$\mathcal{L}^* $$

In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional calculus formal system . The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring processes are fuzzified. A sequence of new extensions { } of the system is proposed, and the completeness of is proved.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

Conditions for Instability of One Class of Nonlinear Nonautomomous Dynamic Systems

Consideration was given to the conditions for instability of the equilibrium states of a nonlinear nonautonomous dynamic systems obeying an ordinary vector differential equation of arbitrary order whose right-hand side satisfies the following conditions: (i) for any t 0, div 0$$ " align="middle" border="0"> almost everywhere on the set H that is a neighborhood of the equilibrium point of the system and (ii) at any point . The equilibrium states of such systems can be both stable and unstable. For one class of these systems, sufficient instability conditions were given, which enables one to carry out studies using only the information about the right-hand side of the system.     

An Algebraic Approach to Propositional Fuzzy Logic

We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield , and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields.     

The inf-sup condition for low order elements on anisotropic meshes

On a large class of two-dimensional anisotropic meshes, the infsup condition (stability) is proved for the triangular and quadrilateral finite element pairs suggested by Bernardi/Raugel and Fortin. As a consequence the pairs , and turn out to be stable independent of the aspect ratio of the elements. Both the visit of the first author in Valenciennes and the visit of the second author in Chemnitz were financed by the DFG (German Research Foundation), Sonderforschungsbereich 393.     

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

A Parallel Logarithmic Order Algorithm for General Multibody System Dynamics

A novel optimal order optimal resource parallel multibody algorithm with general system applicability is derived directly from the sequential recursive methods and the most recent developments in recursive constraint treatments. This new Recursive Coordinate Reduction Parallelism (RCRP) is the first optimal order parallel direct method with a sequential implementation that is exactly the efficient algorithm. Consequently, the RCRP sets new benchmarks for performance over a wide range of problem size and parallel resources. Comparisons to existing methods also demonstrate that the RCRP is presently the best general parallel method.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .     

Two-Parameter Discrete Systems over a Residue Ring and Their Properties

A class of two-parameter discrete systems defined on the ring of class of residues of integers modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability.     

Quaternary Codes and Biphase Sequences from $$\mathbb{Z}_8 $$ -Codes

Composing the Carlet map with the inverse Gray map, a new family of cyclic quaternary codes is constructed from 5-cyclic -codes. This new family of codes is inspired by the quaternary Shanbag–Kumar–Helleseth family, a recent improvement on the Delsarte–Goethals family. We conjecture that these -codes are not linear. As applications, we construct families of low-correlation quadriphase and biphase sequences.     

On Projection Matrices $$\mathcal{P}^k \to \mathcal{P}^2 ,k = 3,...,6, $$ and their Applications in Computer Vision

Projection matrices from projective spaces have long been used in multiple-view geometry to model the perspective projection created by the pin-hole camera. In this work we introduce higher-dimensional mappings for the representation of various applications in which the world we view is no longer rigid. We also describe the multi-view constraints from these new projection matrices (where k > 3) and methods for extracting the (non-rigid) structure and motion for each application.     

Computational Finite-Element Schemes for Optimal Control of an Elliptic System with Conjugation Conditions

New optimal control problems are considered for distributed systems described by elliptic equations with conjugate conditions and a quadratic minimized function. Highly accurate computational discretization schemes are constructed for the case where a feasible control set coincides with the full Hilbert space of controls.     

Computing the Kantorovich Distance for Images

Computing the Kantorovich distance for images is equivalent to solving a very large transportation problem. The cost-function of this transportation problem depends on which distance-function one uses to measure distances between pixels.In this paper we present an algorithm, with a computational complexity of roughly order (N2), where N is equal to the number of pixels in the two images, in case the underlying distance-function is the L1-metric, an approximation of the L2-metric or the square of the L2-metric; a standard algorithm would have a computational complexity of order (N3). The algorithm is based on the classical primal-dual algorithm.The algorithm also gives rise to a transportation plan from one image to the other and we also show how this transportation plan can be used for interpolation and possibly also for compression and discrimination.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.