Complexity bounds for zero-test algorithms

Joris van der Hoeven; John Shackell

doi:10.1016/j.jsc.2006.06.001

Complexity bounds for zero-test algorithms

Joris van der Hoeven
, John Shackell

Université Paris-Saclay
University of Kent

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

8 Citations (Scopus)

Résumé

In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for "witness conjectures".

langue originale	Anglais
Pages (de - à)	1004-1020
Nombre de pages	17
journal	Journal of Symbolic Computation
Volume	41
Numéro de publication	9
Les DOIs	https://doi.org/10.1016/j.jsc.2006.06.001
état	Publié - 1 janv. 2006
Modification externe	Oui

Accès au document

10.1016/j.jsc.2006.06.001

Contient cette citation

@article{7ff39bc225564864b057a7c67f575dc6,

title = "Complexity bounds for zero-test algorithms",

abstract = "In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for {"}witness conjectures{"}.",

keywords = "Complexity, Pfaffian series, Power series, Witness conjecture, Zero-test",

author = "\{van der Hoeven\}, Joris and John Shackell",

year = "2006",

month = jan,

day = "1",

doi = "10.1016/j.jsc.2006.06.001",

language = "English",

volume = "41",

pages = "1004--1020",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

number = "9",

}

TY - JOUR

T1 - Complexity bounds for zero-test algorithms

AU - van der Hoeven, Joris

AU - Shackell, John

PY - 2006/1/1

Y1 - 2006/1/1

N2 - In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for "witness conjectures".

AB - In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for "witness conjectures".

KW - Complexity

KW - Pfaffian series

KW - Power series

KW - Witness conjecture

KW - Zero-test

U2 - 10.1016/j.jsc.2006.06.001

DO - 10.1016/j.jsc.2006.06.001

M3 - Article

AN - SCOPUS:33746912038

SN - 0747-7171

VL - 41

SP - 1004

EP - 1020

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 9

ER -

Complexity bounds for zero-test algorithms

Résumé

Accès au document

Empreinte digitale

Contient cette citation