m
• E

F Nous contacter

0

# Documents  68Q30 | enregistrements trouvés : 58

O

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Second symposium on symbolic and algebraic manipulationproceeding of the... held in los angeles,march 23-25,1971 Petrick, S. R. | A.C.M. 1972

Congrès

Localisation : Colloque 1er étage (LOS)

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Stacs 84 :symposium of theoretical aspects of computer science#April 11-13 Fontet, M. ; Mehlhorn, K. | Springer-Verlag 1985

Congrès

- 431 p.
ISBN 978-0-387-12920-4

Lecture notes in computer science , 0166

Localisation : Collection 1er étage

algorithme # algorithmique # complexité # informatique théorique # langage formel # logique # logique de programmation # logique mathématiques # programme # réseaux # système informatique

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Discrete algorithms and complexity :proceedings of the Japan-u.s. joint seminar#June 4-6 Johnson, D. S. ; Nishizeki, T. ; Nozaki, A. ; Wilf, H. S. | Academic Press Inc. 1987

Congrès

- 486 p.
ISBN 978-0-12-386870-1

Perspectives in computing , 0015

Localisation : Colloque 1er étage (KYOT)

algorithme # co dage # code # complexite des algorithmes # cryptographie # mathematiques discretes # theorie de l' information

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Graph-theoretic concepts in computer science :proceedings of the international workshop wg '86#June 17-19 Schmidt, G. ; Tinhofer, G. | Springer-Verlag 1987

Congrès

- 305 p.
ISBN 978-3-540-17218-5

Lecture notes in computer science , 0246

Localisation : Collection 1er étage

algorithme # architecture et réseau # circuit intégré # classe de complexité # gestion des systèmes informatiques # grammaire # implementation # logique mathématiques # structure des données # système de réecriture

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Logic and machines :proceedings of the symposium#May 23-28 Borger, E. ; Hasenjaeger, G. ; Rodding, D. | Springer-Verlag 1984

Congrès

- 456 p.
ISBN 978-3-540-13331-5

Lecture notes in computer science , 0171

Localisation : Collection 1er étage

algorithme # automate # complexité # indécidabilité # logique # machine

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Coding theory and applications :2nd international colloquium#Nov. 24-26 Cohen, G. ; Godlewski, P. | Springer-Verlag 1988

Congrès

- 196 p.
ISBN 978-3-540-19368-5

Lecture notes in computer science , 0311

Localisation : Collection 1er étage

algorithme # codage # complexité des algorithmes # théorie de l'information # théorie des codes

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## 26th annual symposium on foundations of computer sciencesymposium on... held on oct. 21-23,1985,in portland,oregon | Ieee Computer Society Press 1985

Congrès

ISBN 978-0-8186-0644-1

Localisation : Colloque 1er étage (PONT)

algorithme # automatique # informatique # ordinateur

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Structure in complexity theory :proceedings of the conference held at the university of california#June 2-5 Selman, Alan L. | Springer-Verlag 1986

Congrès

- 400 p.
ISBN 978-3-540-16486-9

Lecture notes in computer science , 0223

Localisation : Collection 1er étage

algorithme # complexité # logique

68Q30

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Algorithms and data structures :2nd workshop, wads'91 held in ottawa#Aug. 14-16 Dehne, F. ; Sack, J. R. ; Santoro, N. | Springer-Verlag 1991

Congrès

- 495 p.
ISBN 978-3-540-54343-5

Lecture notes in computer science , 0519

Localisation : Collection 1er étage

algorithme # algorithmique # énumération # graphe # structure des données

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Algorithms and orderproceedings of the nato advanced study institute held in ottawa,canada,may 31 - june 13,1987 Rival, Ivan | Kluwer Academic Publishers 1989

Congrès

ISBN 978-0-7923-0007-6

Nato a.s.i. series

Localisation : Colloque 1er étage (OTTA)

algorithme # algorithmiqu e # combinatoire # complexite # donnee graphique # ensemble ordonne # informatique graphique # logique # ordre # structure de donnee graphique # structure ordonnee

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Automata, languages, and programming :19th international colloquium#July 13-17 Kuich, W. | Springer-Verlag 1992

Congrès

- 719 p.
ISBN 978-3-540-55719-7

Lecture notes in computer science , 0623

Localisation : Collection 1er étage

algorithme de graphes # algorithme géométrique # analyse d'algorithme # automate fini # calcul parallèle # calcul symbolique # complexité de Kolmogorov # développement de programme # grammaire de graphes # langage # langage formel # logique # modèle # programmation # spécification de temps # sémantique concurrence # équivalence de processus

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Algorithms and computation :Third international symposium, ISAAC'92#Dec. 1992 Ibaraki, Toshihide ; Inagaki, Yasuyoshi ; Iwama, Kazuo | Springer-Verlag 1992

Congrès

- 510 p.
ISBN 978-3-540-56279-5

Lecture notes in computer science , 650

Localisation : Collection 1er étage

algorithme # algorithme combinatoire # algorithme des couleurs # algorithme des graphes # algorithme parallèle # algorithmique # calcul # complexité # graphe # géométrie de l'informatique # stucture des données # théorie de la complexité

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Computing and combinatorics :first annual international conference, COCOON'95#Aug. 24-26 Du, Ding-Zhu ; Li, Ming | Springer 1995

Congrès

- 654 p.
ISBN 978-3-540-60216-3

Lecture notes in computer science , 0959

Localisation : Collection 1er étage

algorithme de graphe # algorithme parallèle # apprentissage # base de données # calcul distribué # combinatoire # conception combinatoire # géométrie informatique # logique distribuée # modèle de machine # planification # théorie de la complexité # tracé de graphe

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Computing and combinatorics :second annual international conference COCOON '96#June 17-19 Cai, Jin-Yi ; Wong, Chak Kuen | Springer 1996

Congrès

- 419 p.
ISBN 978-3-540-61332-9

Lecture notes in computer science , 1090

Localisation : Collection 1er étage

algorithme non numérique # analyse des algorithmes # calcul # combinatoire # complexité des problèmes # grammaire # informatique de la géométrie # informatique théorique # modélisation d'objet # opération et gestion # réseau # réécriture des systèmes # système distribué # système informatique # théorie de l'information algorithmique # théorie des graphes

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Orders, algorithms and applicationsSelected papers presented at the conference ordal'94 took place at the ecole normale supérieure de lyon july Bouchitté, V. ; Habib, M. ; Morvan, M. | Elsevier 1997

Congrès

Theoretical computer science , 0175

Localisation : Colloque 1er étage (LYON)

algorithme # algorithme parallèle # application # architecture # encodage # fonction booléenne # graphe # informatique théorique # problème d'interval # reconnaissance # structure et représentation de treillis # treillis booléens

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## IIIème colloque R.C.P. algorithmiqueNice # 18-20 juin, 1980 Morgenstern, J. | C.N.R.S.;I.N.R.I.A. 1980

Congrès

- pag. multi.

Localisation : Colloque 1er étage (NICE)

algorithmique

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Carleson's Theorem and Schnorr randomness Franklin, Johanna | CIRM H

Multi angle

Research talks;Computer Science;Logic and Foundations

Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ is not Schnorr random, then there is a computable function $f : [-\pi,\pi] \rightarrow \mathbb{C}$ whose Fourier series diverges at $t_0$.
This is joint work with Timothy H. McNicholl, and Jason Rute.
Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ i...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## On centauric subshifts Romashchenko, Andrei | CIRM H

Multi angle

Research talks;Computer Science;Logic and Foundations

We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other hand, these subshifts are complex in the sense of computability theory: all their configurations are non periodic or even non-computable, or all their finite patterns have high Kolmogorov complexity, the Turing degree spectrum is rather sophisticated, etc.
We start with the simplest example of such centaurisme with an SFT that is minimal and contains only aperiodic (and quasiperiodic) configurations. Then we discuss how far these heterogeneous properties can be strengthened without getting mutually exclusive.
This is a joint work with Bruno Durand (Univ. de Montpellier).
We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## A derivation on the field of d.c.e.reals Miller, Joseph | CIRM H

Multi angle

Research talks;Computer Science;Logic and Foundations

Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
$\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.$
converges and is independent of the choice of approximations. Furthermore, they showed that $\partial\alpha/\partial\beta = 1$ if and only if $\alpha-\beta$ is nonrandom; $\partial\alpha/\partial\beta>1$ if and only if $\alpha-\beta$ is a random left-c.e. real; and $\partial\alpha/\partial\beta<1$ if and only if $\alpha-\beta$ is a random right-c.e. real.

We extend their results to the d.c.e. reals, which clarifies what is happening. The extension is straightforward. Fix a random left-c.e. real $\Omega$ with approximation $\{\Omega_s\}_{s\in\omega}$. If $\alpha$ is a d.c.e. real with d.c.e. approximation $\{\alpha_s\}_{s\in\omega}$, let
$\partial\alpha = \frac{\partial\alpha}{\partial\Omega} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\Omega-\Omega_s}.$
As above, the limit exists and is independent of the choice of approximations. Now $\partial\alpha=0$ if and only if $\alpha$ is nonrandom; $\partial\alpha>0$ if and only if $\alpha$ is a random left-c.e. real; and $\partial\alpha<0$ if and only if $\alpha$ is a random right-c.e. real.

As we have telegraphed by our choice of notation, $\partial$ is a derivation on the field of d.c.e. reals. In other words, $\partial$ preserves addition and satisfies the Leibniz law:
$\partial(\alpha\beta) = \alpha\,\partial\beta + \beta\,\partial\alpha.$
(However, $\partial$ maps outside of the d.c.e. reals, so it does not make them a differential field.) We will see how the properties of $\partial$ encapsulate much of what we know about randomness in the left-c.e. and d.c.e. reals. We also show that if $f\colon\mathbb{R}\rightarrow\mathbb{R}$ is a computable function that is differentiable at $\alpha$, then $\partial f(\alpha) = f'(\alpha)\,\partial\alpha$. This allows us to apply basic identities from calculus, so for example, $\partial\alpha^n = n\alpha^{n-1}\,\partial\alpha$ and $\partial e^\alpha = e^\alpha\,\partial\alpha$. Since $\partial\Omega=1$, we have $\partial e^\Omega = e^\Omega$.

Given a derivation on a field, the elements that it maps to zero also form a field: the $\textit {field of constants}$. In our case, these are the nonrandom d.c.e. reals. We show that, in fact, the nonrandom d.c.e. reals form a $\textit {real closed field}$. Note that it was not even known that the nonrandom d.c.e. reals are closed under addition, and indeed, it is easy to prove the convergence of [1] from this fact. In contrast, it has long been known that the nonrandom left-c.e. reals are closed under addition (Demuth [2] and Downey, Hirschfeldt, and Nies [3]). While also nontrivial, this fact seems to be easier to prove. Towards understanding this difference, we show that the real closure of the nonrandom left-c.e. reals is strictly smaller than the field of nonrandom d.c.e. reals. In particular, there are nonrandom d.c.e. reals that cannot be written as the difference of nonrandom left-c.e. reals; despite being nonrandom, they carry some kind of intrinsic randomness.
Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
$\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.$
converges and is independent of the choice of approximations. Furthermore, they showed that ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Randomness connecting to set theory and to reverse mathematics Nies, André | CIRM H

Multi angle

Research talks;Computer Science;Logic and Foundations

I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics. I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of ...

#### Filtrer

##### Codes MSC

Ressources Electroniques (Depuis le CIRM)

Books & Print journals

Recherche avancée

0
Z