Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves

Given a real valued function f(X,Y), a box region B₀⊆R² and ε>0, we want to compute an ε-isotopic polygonal approximation to the restriction of the curve S=f⁻¹(0)={p∈R²:f(p)=0} to B₀. We focus on subdivision algorithms because of their adaptive complexity and ease of implementation. Plantinga & Vegter gave a numerical subdivision algorithm that is exact when the curve S is bounded and non-singular. They used a computational model that relied only on function evaluation and interval arithmetic. We generalize their algorithm to any bounded (but possibly non-simply connected) region that does not contain singularities of S. With this generalization as a subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete purely numerical method to compute isotopic approximations of algebraic curves with isolated singularities.     

Supermigrative semi-copulas and triangular norms

A semi-copula S:[0,1]²→[0,1] is called supermigrative if it is commutative and satisfies S(αx,y)?S(x,αy) for all α∈[0,1] and for all x,y∈[0,1] such that y?x. In this paper, the class of supermigrative semi-copulas is investigated, by focusing, in particular, on the subclass of continuous triangular norms. Some interesting connections with the theory of copulas are also underlined.     

The general α-decomposition problem of fuzzy relations

This paper deals with a general α-decomposition problem of fuzzy relations, which can be stated as follows: given a fuzzy relation R∈F(X×Y), determine two fuzzy relations Q∈F(X×Z) and T∈F(Z×Y) such that , where X (resp. Y) is a finite set. Firstly we point out that every fuzzy relation R is always generally α-decomposable, and give an algorithm to construct Q and T with for a given R. Secondly, we show that the general content ρ(R) with is equal to the chromatic number of the simple graph F_R generated by R. Therefore, finding an exact algorithm for calculating ρ(R) is an NP-complete problem.     

Extensions of MSO and the monadic counting hierarchy

In this paper, we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most¹. In 1 it was shown that the extension of FO by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We consider first certain sublogics of FO(Most¹) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic MSO(Rⁿ)_n∈Z+, where Rⁿ is the nth vectorization of R, corresponds to the Δ₀-fragment of arithmetic. Then we show that FO(Most¹)?MSO(Rⁿ)_n∈Z+ and that, on unary vocabularies, FO(Most¹) collapses to uniform-TC⁰. Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most¹) over the empty vocabulary. On the other hand, over strings, FO(Most¹) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most¹) can express problems complete via first-order reductions for each level of the counting hierarchy.     

An improved algorithm for the red-blue hitting set problem with the consecutive ones property

Let S be a set of elements. We say that a collection C of subsets of S has the consecutive ones property if there exist a linear order on S and a 0-1 matrix M, where Mij=1 if and only if the jth element is in the ith set in C, such that all 1's appear consecutively in each row of M. A set X∈C is hit by a subset S^′⊆S if X∩S^′≠∅. Let Cr (red collection) and Cb (blue collection) be two collections of subsets of S respectively. The red-blue hitting set problem asks for a subset S^′⊆S such that all sets in the blue collection are hit by S^′, while the number of sets in the red collection hit by S^′ has to be minimum. We present a shortest-path based algorithm with time complexity O(|Cb||S|+|Cr||S|+²|S|) for this problem with Cr∪Cb having the consecutive ones property, which improves the previous time bound O(|Cr||Cb|²|S|) by Dom et al. (2008) [8].     

Connectivity-preserving transformations of binary images

A binary image I is B_a, W_b-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a B_a, w_b-connected image I in which a black pixel can be interchanged with an adjacent white pixel provided that this preserves the connectivity of both the foreground and the background of I. We have shown that for any (a, b) ∈ {(4, 8), (8, 4), (8, 8)}, any two B_a, w_b-connected images I and J each with n black pixels differ by a sequence of Θ(n²) interchanges. We have also shown that any two B₄, W₄-connected images I and J each with n black pixels differ by a sequence of O(n⁴) interchanges.     

On the degree of polynomial parameter-dependent Lyapunov functions for robust stability of single parameter-dependent LTI systems: A counter-example to Barmish's conjecture

In this paper, we consider the robust Hurwitz stability analysis problems of a single parameter-dependent matrix A(θ)?A₀+θA₁ over θ∈[-1,1], where A₀,A₁∈R^n×n with A₀ being Hurwitz stable. In particular, we are interested in the degree N of the polynomial parameter-dependent Lyapunov matrix (PPDLM) of the form that ensures the robust Hurwitz stability of A(θ) via . On the degree of PPDLMs, Barmish conjectured in early 90s that if there exists such P(θ), then there always exists a first-degree PPDLM P(θ)=P₀+θP₁ that meets the desired conditions, regardless of the size or rank of A₀ and A₁. The goal of this paper is to falsify this conjecture. More precisely, we will show a pair of the matrices A₀,A₁∈R^3×3 with A₀+θA₁ being Hurwitz stable for all θ∈[-1,1] and prove rigorously that the desired first-degree PPDLM does not exist for this particular pair. The proof is based on the recently developed techniques to deal with parametrized LMIs in an exact fashion and related duality arguments. From this counter-example, we can conclude that the conjecture posed by Barmish is not valid when n?3 in general.     

On the triangle inequalities in fuzzy metric spaces

This paper presents level forms of the triangle inequalities in fuzzy metric spaces (X, d, L, R). To aid discussion, a fuzzy pre-metric condition is introduced. It is first pointed out that under the fuzzy pre-metric condition the first triangle inequality is always equivalent to its level form. The second triangle inequality is equivalent to one level form when R is right continuous, and to another level form also when further conditions are imposed on R. In a fuzzy metric space, the level form of the first triangle inequality and one of the level forms of the second triangle inequality are always valid. The other level form of the second triangle inequality holds for all but at most countable α ∈ [0, 1). Finally, a fixed point theorem for fuzzy metric spaces is derived as an application of the preceding results.     

Flat families by strongly stable ideals and a generalization of Gröbner bases

Let J be a strongly stable monomial ideal in S=K[x₀,…,x_n] and let Mf(J) be the family of all homogeneous ideals I in S such that the set of all terms outside J is a K-vector basis of the quotient S/I. We show that an ideal I belongs to Mf(J) if and only if it is generated by a special set of polynomials, the J-marked basis of I, that in some sense generalizes the notion of reduced Gröbner basis and its constructive capabilities. Indeed, although not every J-marked basis is a Gröbner basis with respect to some term order, a sort of reduced form modulo I∈Mf(J) can be computed for every homogeneous polynomial, so that a J-marked basis can be characterized by a Buchberger-like criterion. Using J-marked bases, we prove that the family Mf(J) can be endowed, in a very natural way, with a structure of an affine scheme that turns out to be homogeneous with respect to a non-standard grading and flat in the origin (the point corresponding to J), thanks to properties ofJ-marked bases analogous to those of Gröbner bases about syzygies.     

Sets of approximating functions with finite Vapnik-Chervonenkis dimension for nearest-neighbors algorithms

According to a certain misconception sometimes met in the literature: for the nearest-neighbors algorithms there is no fixed hypothesis class of limited Vapnik-Chervonenkis dimension.In the paper a simple reformulation (not a modification) of the nearest-neighbors algorithm is shown where instead of a natural number k, a percentage α ∈ (0, 1) of nearest neighbors is used. Owing to this reformulation one can construct sets of approximating functions, which we prove to have finite VC dimension. In a special (but practical) case this dimension is equal to ⌊2/α⌋. It is also then possible to form a sequence of sets of functions with increasing VC dimension, and to perform complexity selection via cross-validation or similarly to the structural risk minimization framework. Results of such experiments are also presented.     

Consensus models: Computational complexity aspects in modern approaches to the list coloring problem

In the paper we study new approaches to the problem of list coloring of graphs. In the problem we are given a simple graph G=(V,E) and, for every v∈V, a nonempty set of integers S(v); we ask if there is a coloring c of G such that c(v)∈S(v) for every v∈V. Modern approaches, connected with applications, change the question—we now ask if S can be changed, using only some elementary transformations, to ensure that there is such a coloring and, if the answer is yes, what is the minimal number of changes. In the paper for studying the adding, the trading and the exchange models of list coloring, we use the following transformations:

•

adding of colors (the adding model): select two vertices u, v and a color c∈S(u); add c to S(v), i.e. set S(v):=S(v)∪{c};

•

trading of colors (the trading model): select two vertices u, v and a color c∈S(u); move c from S(u) to S(v), i.e. set S(u):=S(u)?{c} and S(v):=S(v)∪{c};

•

exchange of colors (the exchange model): select two vertices u, v and two colors c∈S(u), d∈S(v); exchange c with d, i.e. set S(u):=(S(u)?{c})∪{d} and S(v):=(S(v)?{d})∪{c}.

Our study focuses on computational complexity of the above models and their edge versions. We consider these problems on complete graphs, graphs with bounded cyclicity and partial k-trees, receiving in all cases polynomial algorithms or proofs of NP-hardness.     

Some remarks on congruences obtained from the L-fuzzy Nakano hyperoperation

In this paper we study relations which are congruences with respect to ∧ and ?_p, where ?_p is the p-cut of the L-fuzzy hyperoperation ?. The main idea is to start from an equivalence relation R₁ which is a congruence with respect to ∧ and ?₁ and, for each p ∈ X, construct an equivalence relation R_p which is a congruence with respect to ∧ and ?_p. Furthermore, for each x ∈ R_p we construct a quotient hyperoperation ?_p and we show that the hyperalgebra (X/R_p, ?_p) is a join space and the hyperalgebra (X/R_p, ?_p, ∧_p) is a hyperlattice.     

A theoretical limit for safety verification techniques with regular fix-point computations

In computer aided verification, the reachability problem is particularly relevant for safety analyses. Given a regular tree language L, a term t and a relation R, the reachability problem consists in deciding whether there exist a positive integer n and terms t₀,t₁,…,tn such that t₀∈L, tn=t and for every 0?i<n, (ti,ti+1)∈R. In this case, the term t is said to be reachable, otherwise it is said unreachable. This problem is decidable for particular kinds of relations, but it is known to be undecidable in general, even if L is finite. Several approaches to tackle the unreachability problem are based on the computation of an R-closed regular language containing L. In this paper we show a theoretical limit to this kind of approaches for this problem.     

A combinatorial property on angular orders of plane point sets

We study the following combinatorial property of point sets in the plane: For a set S of n points in general position and a point p∈S consider the points of S−p in their angular order around p. This gives a star-shaped polygon (or a polygonal path) with p in its kernel. Define c(p) as the number of convex angles in this star-shaped polygon around p, and c(S) as the sum of all c(p), for p∈S. We show that for every point set S, c(S) is always at least . This bound is shown to be almost tight. Consequently, every set of n points admits a star-shaped polygonization with at least convex angles.     

On the structure of generalized rough sets

In this paper we consider some fundamental properties of generalized rough sets induced by binary relations on algebras and show that

1.

Any reflexive binary relation determines a topology.

2.

If θ is a reflexive and symmetric relation on a set X, then O={A⊆X|θ_-(A)=A} is a topology such that A is open if and only if it is closed.

3.

Conversely, for every topological space (X,O) satisfying the condition that A is open if and only if it is closed, there exists a reflexive and symmetric relation R such that O={A⊆X|R_-(A)=A}.

4.

Let θ be an equivalence relation on X. For any pseudo ω-closed subset A of X, θ₋(A) is an ω-closed set if and only if ω(x, x, … , x) ∈ θ₋(A) for any x ∈ X.

Moreover we consider properties of generalized rough sets.     

Bernstein-type operators which preserve polynomials

In this paper we present the sequence of linear Bernstein-type operators defined for f∈C[0,1] by B_n(f°τ⁻¹)°τ, B_n being the classical Bernstein operators and τ being any function that is continuously differentiable ∞ times on [0,1], such that τ(0)=0, τ(1)=1 and τ^′(x)>0 for x∈[0,1]. We investigate its shape preserving and convergence properties, as well as its asymptotic behavior and saturation. Moreover, these operators and others of King type are compared with each other and with B_n. We present as an interesting byproduct sequences of positive linear operators of polynomial type with nice geometric shape preserving properties, which converge to the identity, which in a certain sense improve B_n in approximating a number of increasing functions, and which, apart from the constant functions, fix suitable polynomials of a prescribed degree. The notion of convexity with respect to τ plays an important role.     

Fast algorithms for minimum matrix norm with application in computer graphics

In this paper we consider the following problem. Given (r ₁,r ₂, ...,r _n) R ⁿ, for anyI= (I ₁,I ₂,...,I _n) Z ⁿ, letE ₁=(e _ij), wheree _ij=(r _i–r_j)–(I _i–I_j), findI Z ⁿ such that |E _I| is minimized, where |·| is a matrix norm. This problem arises from optimal curve rasterization in computer graphics, where minimum distortion of curve dynamic context is sought. Until now, there has been no polynomial-time solution to this computer graphics problem. We present a very simpleO(n lgn)-time algorithm to solve this problem under various matrix norms.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant OGP0046373.     

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I^k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in , when this ratio is smaller than . This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R⁻ schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R⁻ schemes, becomes useless. Besides, we believe that our algorithm is of independent interest.     

Binary search with delayed and missing answers

How many questions are necessary and sufficient to guess an unknown number x in the set S={1,2,…,n}, by using only comparison questions, that is questions of the type “Is x?a?”, a∈S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d?0 and c=1.