Aller à : contenu haut bas recherche

EN     FR
Vous êtes ici:   UNIL > HEC Inst. > HEC App. > RECHERCHE

## Jacques Duparc

### Coordonnées

 Professeur ordinaire ContactJacques.Duparc@unil.chInternef, bureau 134Tél 021.692.35.88Adresse postaleUniversité de LausanneQuartier UNIL-DorignyBâtiment Internef1015 Lausanne Page personnelle : people.epfl.ch/jacques.duparc

### Enseignements

 bachelor Introduction à la logique Formation concernée Baccalauréat universitaire ès Sciences en management

### Axes de recherche

Borel mappings via games and representation theorems
We characterize some classes of Borel functions over the Baire space as strategies in suitable games. This is a way towards both obtaining representation theorems and elaborating a fine classifications of Borel functions. Representation theorems come as a representation of some classes of functions very different from their definitions. For instance, a cornerstone for this type of result is the Baire Grand Theorem which states that the following are equivalent for any function f on a Polish space:

- f is the pointwise limit of countably many continuous functions;
- on every non-empty closed subset f admits a point of continuity.

Continuous Reductions on Quasi-Polish spaces
Quasi-Polish spaces is a novel unifying theory due to Matthew de Brecht. It brings together topological structures that were previously unrelated. It connects closely topology in mathematical analysis -- which is usually Hausdorff (T_2) -- to topology in computer science -- which is rather Kolmogorov} (T_0) -- by offering the Polish spaces as well as the omega-algebraic or omega-continuous domains a common roof. Quasi-Polish spaces are derived from Polish spaces -- which are separable completely metrizable topological spaces -- by simply relaxing the symmetry condition in the definition of a metric.

We propose to design and make use of game theoretical tools to study the reductions between these sets and explore the underlying ordering as well as
the natural hierarchies that would arise. We intend to do this in a similar manner as the way we studied the Wadge hierarchy of Borel subsets of the Cantor space.

Quotients of Projective Fraïssé Limits
The idea of studying infinite structures via approximation by finite structures is a well rooted concept in mathematics. In particular, the Fraïssé limit is an extensively studied tool in many areas of mathematics.
In 2006 T. Irwin and S. Solecki introduced the projective Fraïssé limit of topological structures. Many applications have since been found in continua theory and descriptive dynamics.
We propose to isolate and study the class of all compact metric spaces that are obtainable as a quotient of a projective Fraïssé limit by the interpretation of a binary relation symbol from the language. Our hope is to describe a natural way of obtaining such spaces.

Over a century ago, the modern theory of integration, based on measure theory induced a fundamental interest in the study of well-behaved subsets of the real line or the real plane. Topology, which developed about the same time yielded the mathematical framework for such a study. For instance, the σ-algebra generated by the open subsets proved to be central in measure theory, for the sets it defines bear all desired nice properties.

The most refined classification of these sets is the so-called Wadge hierarchy whose study involves methods from (set theoretical) game theory

Topological Complexity, Games, Logic and Automata
We try to unravel the fine topological structure of omega-regular tree languages which are the infinitary languages of trees recognized by automata. In other words, we exhibit the Wadge hierarchy of non deterministic omega-tree automata.

### Assistants

 Gianluca Basso gianluca.basso@unil.ch Alessia Spadini alessia.spadini@unil.ch Louis Vuilleumier louis.vuilleumier.1@unil.ch

### Publications

48 dernières publications classées par: type de publication  -  année

: Revue avec comité de lecture

### Articles

 Camerlo Riccardo , Duparc Jacques (2017). Some remarks on Baire's grand theorem. Archive for Mathematical Logic.

 Cabessa J. , Duparc J. (2016). Expressive Power of Nondeterministic Recurrent Neural Networks in Terms of their Attractor Dynamics. International Journal of Unconventional Computing, 12, 25-50.

 Duparc J. (2015). Easy Proofs of Löwenheim-Skolem Theorems by Means of Evaluation Games. CoRR, abs/1507.03665.

 Cabessa J. , Duparc J. (2009). A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy: Part II. RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications, 43, 463-515.

 Cabessa J. , Duparc J. (2008). The Algebraic Counterpart of the Wagner Hierarchy. Lecture Notes in Computer Science, 5028, 100-109.

 Duparc J. , Finkel O. (2007). Wadge games and sets of reals recognized by simple machines: An omega power of a finite context-free language which is Borel above Delta^ø_omega. Studies in Logic, 11, 109-122.

 Duparc J. , Riss M. (2006). The Missing Link for omega-Rational Sets, Automata, and Semigroups. International Journal of Algebra and Computation, 16, 161-185.

 Duparc J. (2003). A Hierarchy of Deterministic Context-Free omega-languages. Theoretical Computer Science, 290, 1253-1300.

 Duparc J. (2003). The Steel Hierarchy of Ordinal Valued Borel Mappings. Journal of Symbolic Logic, 68, 187-234.

 Duparc J. (2001). Wadge Hierarchy and Veblen Hierarchy. Part I: Borel Sets of Finite Rank. Journal of Symbolic Logic, 66, 56-86.

 Duparc J., Finkel O. ; Ressayre J-P. (2001). Computer Science and the Fine Structure of Borel Sets. Theoretical Computer Science, 257, 85-105.

 Duparc J. (1999). The Normal Form of Borel Sets. Part II: Borel Sets of Infinite Rank. Comptes Rendus de l'Académie des Sciences - Series I - Mathematics, 328, 735-740.

 Duparc J. (1995). The Normal Form of Borel Sets. Part I: Borel Sets of Finite Rank. Comptes Rendus de l'Académie des Sciences - Series I - Mathematics, 320, 651-656.

### Livres

 Duparc J. (2015). La Logique Pas à Pas. Presses polytechniques et universitaires romandes.

### Parties de livre

 Duparc J. (2017). Jeux, Topologie et Automates. Informatique Mathématique: Une photographie en 2017 (pp. 55-79). CNRS Éditions.

 Duparc J., Finkel O. ; Ressayre J-P. (2014). The Wadge Hierarchy of Petri Nets omega-Languages. Logic, Computation, Hierarchies (Vol. 4, pp. 109-138). De Gruyter.

 Arnold A., Duparc J., Murlak F. ; Niwiński D. (2007). On the topological complexity of tree languages. Logic and Automata: History and Perspectives (Vol. 2, pp. 9-28). Amsterdam University Press.

### Actes de conférence (partie)

 Cabessa J. , Duparc J. (2015, Jan). Expressive Power of Non-deterministic Evolving Recurrent Neural Networks in Terms of Their Attractor Dynamics. Unconventional Computation and Natural Computation: 14th International Conference, UCNC 2015, Auckland, New Zealand, August 30 - September 3, 2015, Proceedings, 9252 (pp. 144-156). Springer, Cham.

 Duparc J. , Fournier K. (2015, Jan). A Tentative Approach for the Wadge-Wagner Hierarchy of Regular Tree Languages of Index [0, 2]. Descriptional Complexity of Formal Systems: 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, 9118 (pp. 81-92). Springer, Cham.

 Duparc J., Finkel O. ; Ressayre J.-P. (2013, Jan). The Wadge Hierarchy of Petri Nets \emph$$\omega$$-Languages. Logical Foundations of Computer Science, International Symposium, LFCS 2013, San Diego, CA, USA, January 6-8, 2013. Proceedings, 7734 (pp. 179-193).

 Duparc J., Facchini A. ; Murlak F. (2011, Jan). Definable Operations On Weakly Recognizable Sets of Trees. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, December 12-14, 2011, Mumbai, India, 13 (pp. 363-374).

 Cabessa J., Duparc J., Facchini A. ; Murlak F. (2009, Déc). The Wadge Hierarchy of Max-Regular Languages. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), 4 (pp. 121-132). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

 Duparc J. , Facchini A. (2009, Jan). A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata. Selected Papers of the International Conference Infinity in Logic and Computation, Cape Town, South Africa, November 2007, 5489 (pp. 46-55). Springer.

 Duparc J., Facchini A. ; Murlak F. (2009, Jan). Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata. Computer Science Logic: 23rd International Workshop, CSL 2009, 18th Annual Conference of the EACSL, Coimbra, Portugal, September 7-11, 2009, Proceedings, 5771 (pp. 225-239). Springer.

 Duparc J. , Facchini A. (2008, Jan). Describing the Wadge Hierarchy for the Alternation Free Fragment of μ -Calculus (I) The Levels Below ω 1. Logic and Theory of Algorithms : Fourth Conference on Computability in Europe, CiE 2008, Athens, Greece, June 2008, Proceedings, 5028 (pp. 186-195). Springer.

 Cabessa J. , Duparc J. (2007, Jan). An inﬁnite game on omega-semigroups. Inﬁnite Games, Papers of the conference Foundations of the Formal Sciences V, held in Bonn, November 26-29, 2004, 11 (pp. 63-78). College Publications, London.

 Duparc J. , Finkel O. (2007, Jan). An ω-power of a ﬁnite context-free language which is Borel above ∆0ω. Inﬁnite Games, Papers of the conference Foundations of the Formal Sciences V, held in Bonn, November 26-29, 2004, 11 (pp. 109-122). College Publications, London.

 Duparc J. , Henzinger T.A. (2007, Sep). Computer Science Logic. 21st International Workshop, CSL 2007 16th Annual Conference of the EACSL Lausanne, Switzerland, 4646. Springer.

 Duparc J. , Murlak F. (2007, Jan). On the Topological Complexity of Weakly Recognizable Tree Languages. Fundamentals of Computation Theory : 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings, 4639 (pp. 261-273). Springer.

 Bradfield J., Duparc J. ; Quickert S. (2005, Jan). Transfinite extension ot the mu-calculus. Computer Science Logic : 19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005. Proceedings, 3634 (pp. 384-396). Springer Berlin / Heidelberg.

 Duparc J. (2003, Jan). Positive Games and persistent Strategies. 12th Annual Conference of the European Association for Computer Science Logic, 2803 (pp. 183-196). Springer.

 Cachat T., Duparc J. ; Thomas W. (2002, Jan). Solving Pushdown Games with a ∑3 Winning Condition. Computer Science Logic : 11th Annual Conference of the EACSL Edinburgh, Scotland, UK, September 22–25, 2002 Proceedings, 2471 (pp. 322-336). Springer.

 Duparc J., Finkel O. ; Ressayre J-P. (2000, Jan). Infinite Games, Finite Machines. Proceedings of the Joint Conference of the 5th Barcelona Logic Meeting and the 6th Kurt Gödel colloquium, Collegium Logicum, Annals of the Kurt-Gödel-Society Vol 4, 2000.

 Duparc J. (1994, Jan). The Normal Form of Borel Sets of Finite Rank. Contributed Papers of the Logic Colloquium'94.

### Rapports

 Duparc J. , Facchini A. (2009). The Topological Complexity of Models of the Modal μ-Calculus: On The Alternation Free Fragment and Beyond. Laboratoire Bordelais de Recherche en Informatique et Université de Lausanne.

### Thèses

 Fournier K., Duparc J. (Dir.) (2016). The Wadge Hierarchy: Beyond Borel Sets. Université de Lausanne, Faculté des hautes études commerciales.

 Carroy R., Duparc J. , Finkel O. (Dir.) (2013). Fonctions de première classe de Baire. Université de Lausanne, Faculté des hautes études commerciales.

 Bach C. W., Jacques D. , Hans P. (Dir.) (2010). Interactive Epistemology and Reasoning: On the Foundations of Game Theory. Université de Lausanne, Faculté des hautes études commerciales.

 Facchini A., Duparc J. (Dir.) (2010). A study on the expressive power of some fragments of the modal µ-Calculus. Université de Lausanne, Faculté des hautes études commerciales.

 Cabessa J., Duparc J. (Dir.) (2007). A game theoretical approach to the algebraic counterpart of the Wagner hierarchy. Université de Lausanne, Faculté des hautes études commerciales.

 Duparc J. (1995). La Forme Normale des Boréliens de Rang fini. University Paris 7.

### Non publié

 Duparc J. (In Press). Wadge Degrees of Louveau's (Wadge) Classes.

 Duparc J. (In Press). A Coarsification of the Wagner Hierarchy.

 Duparc J. (In Press). A Normal Form for Borel Sets.

 Duparc J. (In Press). Anti-Chains of Mappings from omega^omega on some BQO.

 Duparc J. (In Press). Wadge Hierarchy and Veblen Hierarchy. Part II: Borel Sets of Infinite Rank.

 Duparc J. (2008). A Normal Form of Borel Sets of Finite Rank.

### Autres

 Duparc J. , Cabessa J. (2004). Games on Semigroups.

### Compétences

Cours donnés à l'EPFL

Logique mathématique
Fondement des mathématiques (théorie des ensembles) et fondement de l'informatique (informatique théorique).

### Formations

Doctorat de mathématiques
Université Paris VII-Denis Diderot, (1995)

### Mots-clés

• informatique théorique
• logique mathématique
• théorie descriptive des ensembles

 Recherche dans HEC App.   dans tout l'UNIL   dans l'Annuaire
Internef - CH-1015 Lausanne - Suisse  -   Tél. +41 21 692 33 00  -   Fax +41 21 692 33 05