Andrei Gabrielov, Nicolai Vorobjov
Abstract. We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of their approximations by compact o-minimal sets. In particular, we improve the known upper bounds on...
Gabrielov, A, Vorobjov, Nicolai
We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of their approximations by compact o-minimal sets. In particular, we improve the known upper bounds on Betti...
Gabrielov, Andrei, Vorobjov, Nicolai
We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of their approximations by compact o-minimal sets. In particular, we improve the known upper bounds on Betti...
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...
doi:10.1112/jlms/jdm069 ON THE NUMBER OF HOMOTOPY TYPES OF FIBRES OF A DEFINABLE MAP (2008)
Saugata Basu, Nicolai Vorobjov
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...
Safety Properties Verification for Pfaffian Dynamics (2008)
Margarita Korovina, Nicolai Vorobjov
We investigate the behavior of a Pfaffian dynamical system with respect to invariants which formalise safety properties. We study continuous dynamical systems which are called Pfaffian, and first...
On the number of homotopy types of fibres of a definable map (2008)
Saugata Basu, Nicolai Vorobjov
Abstract. 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...
Department of Mathematical Sciences, (2007)
Dima Grigoriev, Nicolai Vorobjov, Ba Ay
Let F be an algebraically closed field of zero characteristic, a polynomial ' 2 F[X1; : : : ; Xn] have a multiplicative complexity r and f1; : : : ; fk 2 F[X1; : : : ; Xn] be some polynomials of...
compatible with a semianalytic (2007)
Savvas Pericleous, Nicolai Vorobjov, Ba Ay
complexity bounds for cylindrical decompositions of sub-Pfaan sets
Savvas Pericleous, Nicolai Vorobjov, Ba Ay, Ba Ay
complexity bounds for cylindrical decompositions of sub-Pfaffian sets [Extended abstract]
Gabrielov, Andrei, Vorobjov, Nicolai
We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of their approximations by compact o-minimal sets. In particular, we improve the known upper bounds on Betti...
On the number of homotopy types of fibres of a definable map (2007)
Basu, Saugata, Vorobjov, Nicolai
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...
Bounds on Sizes of Finite Bisimulations of Pfaffian Dynamical Systems (2006)
Korovina, M., Vorobjov, Nicolai
We study finite bisimulations of dynamical systems in R-n defined by Pfaffian maps. The pure existence of finite bisimulations for a more general class of o-minimal systems was shown in Brihaye et...
On the number of homotopy types of fibres of a definable map (2006)
Basu, Saugata, Vorobjov, Nicolai
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 Dynamical Systems (2006)
Korovina, Margarita, Vorobjov, Nicolai
In this paper we study a class of dynamical systems defined by Pfaffian maps. It is a sub-class of o-minimal dynamical systems which capture rich continuous dynamics and yet can be studied using...
Andrei Gabrielov, Andrei Gabrielov, Nicolai Vorobjov, Nicolai Vorobjov
Abstract. Let X be a semialgebraic set in R n defined by a Boolean combination of atomic formulae of the kind h ∗ 0where∗∈{>, ≥,=}, deg(h) <d, and the number of distinct polynomials h...
Pfaffian hybrid systems (2004)
Margarita Korovina, Nicolai Vorobjov
Abstract. 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...
Complexity of computations with Pfaffian and Noetherian functions (2004)
Andrei Gabrielov, Nicolai Vorobjov
This paper is a survey of the upper bounds on the complexity of basic algebraic and geometric operations with Pfaffian and Noetherian functions, and with sets definable by these functions. Among...
Complexity of cylindrical decompositions of sub-Pfaffian sets (2001)
Andrei Gabrielov, Nicolai Vorobjov
Abstract. We construct an algorithm for a cylindrical cell decomposition of aclosedcubeI n ⊂ R n compatible with a “restricted ” sub-Pfaffian subset Y ⊂ I n, provided an oracle deciding...
Complexity Of Cylindrical Decompositions Of Sub-Pfaffian Sets (1999)
Andrei Gabrielov, Nicolai Vorobjov
We construct an algorithm for a cylindrical cell decomposition of a closed cube I n # R n compatible with a "restricted" sub-Pfaffian subset Y # I n , provided an oracle deciding...
Dima Grigoriev, Nicolai Vorobjov
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...
Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees (1995)
Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
We introduce a new method of proving lower bounds on the depth of algebraic decision trees of degree d and apply it to prove a lower bound \Omega\Gammand/ N ) for testing membership to an...
Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees (1994)
Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \Omega\Gammand/ N) for testing membership to a convex polyhedron having N...
Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees (1994)
Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov, A. Bjorner, L. Lovasz, A. Yao [b
We introduce a new method of proving lower bounds on the depth of algebraic d-degree decision (resp. computation) trees and apply it to prove a lower bound \Omega\Gammand/ N) (resp.\Omega\Gammaesp N=...
Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees (1994)
Dima Grigoriev Marek, Marek Karpinski, Nicolai Vorobjov
We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \Omega\Gammand/ N) for testing membership to a convex polyhedron having N...
Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees (1994)
Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \Omega\Gammand/ N) for testing membership to a convex polyhedron having N...
Complexity of Null- and Positivstellensatz Proofs
Dima Grigoriev, Nicolai Vorobjov
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...