Theory of contact for geometric continuity of parametric curves

This paper develops a theory of contact for piecewise parametric curves based on the differential geometry of evolutes, polar curves, and binormal indicatrices. This theory is completely geometric, independent of parametrization and generalizes to any order. Two sets of dimensionless, characteristic numbers describing the local geometry of a curve up tonth order are defined. These characteristic numbers can be used to describe conditions for higher order contacts in an algebraic fashion. The same characteristic numbers can also be used to interpret contact conditions of up tonth order in terms of the geometry of higher evolutes and binormal indicatrices. The resulting geometric contact conditions are used to design piecewise parametric curves for Computer Aided Geometric Design (CAGD) applications.     

Monoïdes syntactiques des langages algébriques

Summary Syntactic monoids have been considered so far almost only for rational (= regular) languages. We start here a systematic study of the syntactic monoids of algebraic (= context-free) languages. We exhibit a whole class of finitely generated monoids, none of which is isomorphic to the syntactic monoid of an algebraic language. We show that if M ₁ and M ₂ are syntactic monoids of algebraic languages L ₁ and L ₂, and if neither M ₁ nor M ₂ has a zero, then there exists an algebraic language L whose syntactic monoid is isomorphic to the direct product M ₂×M₂. We then prove that the algebraic language ¯L ₀ Complement of {n ⁿ yⁿ zⁿ; n1} has a syntactic monoid M ₀ such that M ₀×M ₀ is not isomorphic to the syntactic monoid of any algebraic language, whence follows that any algebraic language L whose syntatic monoid is isomorphic to M ₀ must be non deterministic.     

An exponential lower bound on the size of algebraic decision trees for Max

We prove an exponential lower bound on the size of any fixed degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n— 1 lower bound of [Rabin (1972)] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on the size of the polyhedral decision problem MAX= for testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraph on n vertices. Received: 15 April 1996     

On the Validity of Implicitization by Moving Quadrics for Rational Surfaces with No Base Points

Techniques from algebraic geometry and commutative algebra are adopted to establish sufficient polynomial conditions for the validity of implicitization by the method of moving quadrics both for rectangular tensor product surfaces of bi-degree (m, n) and for triangular surfaces of total degree n in the absence of base points.     

A lower bound for randomized algebraic decision trees

We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an (n ²)randomized lower bound for theKnapsack Problem, and an (n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.     

A note on autodense related languages

In this paper, some algebraic properties of autodense languages and pure autodense languages are studied. We also investigate the algebraic properties concerning anti-autodense languages. The family of anti-autodense languages contains infix codes, comma-free codes, and some subfamilies of new codes which are anti-autodense prefix codes, anti-autodense suffix codes and anti-autodense codes. The relationships among these subfamilies of new codes are investigated. The characterization of L ⁿ , n ≥ 2, which are anti-autodense is studied.     

On pole assignment of linear systems by gain output feedback

In this paper, the Geometric Approach is used to derive in a straightforward way a sufficient condition for pole assignability by gain output feedback. This result leads to a pole assignment procedure which reduces to solving a system of min (n - m, n - p) polynomial equations where n is the number of states, m the number of inputs, p the number of outputs. In the case where m + p > n, this system clearly appears to be linear. The degrees of freedom related to the pole assignment problem are expressed in terms of (right or left) eigenvectors.     

Construction of 1-resilient Boolean functions with optimum algebraic immunity

In this paper, for an integer n≥10, two classes of n-variable Boolean functions with optimum algebraic immunity (AI) are constructed, and their nonlinearities are also determined. Based on non-degenerate linear transforms to the proposed functions, we can obtain 1-resilient n-variable Boolean functions with optimum AI and high nonlinearity if n?1 is never equal to any power of 2.     

Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.     

Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach

This paper considers the problem of determining the solution set of polynomial systems, a well‐known problem in control system analysis and design. A novel approach is developed as a viable alternative to the commonly employed algebraic geometry and homotopy methods. The first result of the paper shows that the solution set of the polynomial system belongs to the kernel of a suitable symmetric matrix. Such a matrix is obtained via the solution of a linear matrix inequality (LMI) involving the maximization of the minimum eigenvalue of an affine family of symmetric matrices. The second result concerns the computation of the solution set from the kernel of the obtained matrix. For polynomial systems of degree m in n variables, a basic procedure is available if the kernel dimension does not exceed m+1, while an extended procedure can be applied if the kernel dimension is less than n(m?1)+2. Finally, some application examples are illustrated to show the features of the approach and to make a brief comparison with polynomial resultant techniques. Copyright © 2003 John Wiley & Sons, Ltd.     

Polynomial methods for the structured singular value with real parameters

We consider the structured singular value problem with real parametric uncertainty only. Using techniques from algebraic geometry, we propose two algorithms that in principle can yield the precise value of the structured singular value at a fixed frequency. Their ability to do so depends upon their ability to find all common roots to a system of polynomial equations. The first algorithm is applicable to problems with two real parameters each of multiplicity two. The second algorithm is applicable to problems with n distinct real parameters. These algorithms have proved useful in applications to aerospace control law analysis.     

Some new results on the algebraic characterizations of an equality constrained optimization problem equivalent to the transportation problem

An equality constrained optimization problem equivalent to the transportation problem with m sources and n destinations is described. The optimality condition and some algebraic characterizations of the problem are investigated using its Hessian matrix. In addition, several algebraic characterizations of an equivalent case of the transportation problem are given using the spectral decomposition and generalized inverses of its coefficient matrix. It is shown that the transportation problem and its equivalent case have common algebraic characterizations.     

Construction of 1-Resilient Boolean Functions with Optimal Algebraic Immunity and Good Nonlinearity

This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in associative classes. For some n, a part of 1-resilient functions with maximum algebraic immunity constructed in the paper can achieve almost optimal nonlinearity. Apart from their high nonlinearity, the functions reach Siegenthaler's upper bound of algebraic degree. Also a class of 1-resilient functions on any number n > 2 of variables with at least sub-optimal algebraic immunity is provided.     

Stochastic adaptive pole-zero assignment with convergence analysis

The adaptive control u_n is designed for the stochastic system A(z)y_n+1 = B(z)u_n+C(z)w_n+1 with unknown constant matrix coefficients in the polynomials A(z), B(z) and C(z) in the shift-back operator with the purposes that (1) the unknown matrices are strongly consistently estimated and (2) the poles and zeros are replaced in such a way that the system itself is transferred to A⁰(z)y_n+1 = B⁰(z)u_n⁰+_n+1 with given A⁰(z), B⁰(z) and u_n⁰ so that the pole-zero assignment error {_n+1} is minimized. The problem of adaptive pole-zero assignment combined with tracking is also considered in this paper. Conditions used are imposed only on A(z), B(z) and C(z).     

Asymptotic speed-ups in constructive solid geometry

We convert constructive solid geometry input to explicit representations of polygons, polyhedra, or more generallyd-dimensional polyhedra, in time and space 0(n^d), improving a previous0(n^d logn) time bound. We then show that any Boolean formula can be preprocessed in time0(n log n/log logn) and linear space so that the value of the formula can be maintained, as variables are changed one by one, in time O(log n/log logn) per change; this speeds up certain output-sensitive algorithms for constructive solid geometry.     

Approximations in <Emphasis Type="Italic">n</Emphasis>-ary algebraic systems

Algebraic systems have many applications in the theory of sequential machines, formal languages, computer arithmetics, design of fast adders and error-correcting codes. The theory of rough sets has emerged as another major mathematical approach for managing uncertainty that arises from inexact, noisy, or incomplete information. This paper is devoted to the discussion of the relationship between algebraic systems, rough sets and fuzzy rough set models. We shall restrict ourselves to algebraic systems with one n-ary operation and we investigate some properties of approximations of n-ary semigroups. We introduce the notion of rough system in an n-ary semigroup. Fuzzy sets, a generalization of classical sets, are considered as mathematical tools to model the vagueness present in rough systems.     

Multiple View Geometry of General Algebraic Curves

We introduce a number of new results in the context of multi-view geometry from general algebraic curves. We start with the recovery of camera geometry from matching curves. We first show how one can compute, without any knowledge on the camera, the homography induced by a single planar curve. Then we continue with the derivation of the extended Kruppa's equations which are responsible for describing the epipolar constraint of two projections of a general algebraic curve. As part of the derivation of those constraints we address the issue of dimension analysis and as a result establish the minimal number of algebraic curves required for a solution of the epipolar geometry as a function of their degree and genus.We then establish new results on the reconstruction of general algebraic curves from multiple views. We address three different representations of curves: (i) the regular point representation in which we show that the reconstruction from two views of a curve of degree d admits two solutions, one of degree d and the other of degree d(d – 1). Moreover using this representation, we address the problem of homography recovery for planar curves, (ii) dual space representation (tangents) for which we derive a lower bound for the number of views necessary for reconstruction as a function of the curve degree and genus, and (iii) a new representation (to computer vision) based on the set of lines meeting the curve which does not require any curve fitting in image space, for which we also derive lower bounds for the number of views necessary for reconstruction as a function of curve degree alone.     

Lanczos <Emphasis Type="Italic">τ</Emphasis>-method regularization algorithm and its algebraic-programming implementation

An algebraic algorithm is developed for computing an algebraic polynomial y _n of order n ∈ N in computer algebra systems. This polynomial is the optimal approximation of the solution y = y(x), x ∈ [a,b], to a system of linear differential equations with polynomial coefficients and initial conditions at a regular singular zero point of this equation in a space C_{[ a,b ]}^k C_{\left[ {a,b} \right]}^k .     

Easy lower bound for a strange computational model

The paper gives a new proof of the well-known lower bound (n logn) for the algebraic complexity of the functionx ₁ ⁿ x ₂ ⁿ +...+x _n ⁿ (if the characteristic of the ground field does not dividen). As a tool, the proof uses a computational model that counts only duplicators.