Andrei Gabrielov, Nicolai Vorobjov, Bath Ba Ay, Of A. Gabrielov, N. Vorobjov
Abstract. Let X be a semialgebraic set in R n defined by a Boolean combination of atomic formulae of the kind h ∗ 0 where ∗∈{>, ≥, =}, deg(h) <d, and the number of distinct polynomials...
A. Gabrielov, N. Vorobjov, T. Zell
Let X be a subset in [−1,1] n0 ⊂ Rn0 defined by a formula X = {x0 | Q1x1Q2x2...Qνxν((x0,x1,...,xν) ∈ Xν)}, where Qi ∈ {∃, ∀}, Qi � = Qi+1, xi ∈ Rni,and Xν be either an open or a...
On the number of homotopy types of fibres of a definable map (2007)
In this paper we prove a single exponential upper bound on the number of possible homotopy types of the fibres of a Pfaffian map in terms of the format of its graph. In particular, we show that if a...
Upper and lower bounds on sizes of finite bisimulations of Pfaffian hybrid systems (2006)
In this paper we study a class of hybrid systems defined by Pfaffian maps. It is a sub-class of o-minimal hybrid systems which capture rich continuous dynamics and yet can be studied using finite...
Betti numbers of semialgebraic sets defined by quantifier-free formulae (2005)
Let X be a semialgebraic set in R-n defined by a Boolean combination of atomic formulae of the kind h * 0 where * is an element of { >, greater than or equal to, = }, deg(h) < d, and the number of...
Pfaffian hybrid systems (2004)
It is well known that in an o-minimal hybrid system the continuous and discrete components can be separated, and therefore the problem of finite bisimulation reduces to the same problem for a...
Betti numbers of semialgebraic and sub-Pfaffian sets (2004)
Gabrielov, A., Vorobjov, N., Zell, T.
Let X be a subset in [-1, 1](n0) subset of R-n0 defined by the formula X = {x(0) \ Q(1)x(1) Q(2)x(2) ... Q(v)x(v) ((x(0), x(1), ...,x(v)) is an element of X-v)}, where Q(i) is an element of {There...
The complexification and degree of a semi-algebraic set (2002)
The complexification of a semi-algebraic set S subset of R-n is the smallest complex algebraic set containing S. Let S be defined by 8 polynomials of degrees less than d. We prove that the geometric...
Complexity of null- and Positivstellensatz proofs (2002)
We introduce two versions of proof systems dealing with systems of inequalities: Positivstellensatz refutations and Positivstellensatz calculus. For both systems we prove the lower bounds on degrees...
Complexity of cylindrical decompositions of sub-Pfaffian sets (2001)
We construct an algorithm for a cylindrical cell decomposition of a closed cube I(n)subset ofR(n) compatible with a "restricted" sub-Pfaffian subset Y subset ofI(n), provided an oracle deciding...
Complexity Lower Bounds For Computation Trees With Elementary Transcendental Function Gates (1996)
. We consider computation trees which admit as gate functions along with the usual arithmetic operations also algebraic or transcendental functions like exp, log, sin, square root (defined in the...