BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Dominique Lecomte

Dominique Lecomte appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.LOmath.GNFormal Languages and Automata TheoryLogic in Computer Science

Catalog footprint

What is connected

14works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2020arXiv

Descriptive Set Theory and $ω$-Powers of Finitary Languages

The $ω$-power of a finitary language L over a finite alphabet $Σ$ is the language of infinite words over $Σ$ defined by L $\infty$ := {w 0 w 1. .. $\in$ $Σ$ $ω$ | $\forall$i $\in$ $ω$ w i $\in$ L}. The $ω$-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like B{ü}chi automata or B{ü}chi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and $ω$-powers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On small analytic relations

We study the class of analytic binary relations on Polish spaces, compared with the notions of continuous reducibility or injective continuous reducibility. In particular, we characterize when a locally countable Borel relation is $Σ$ 0 $ξ$ (or $Π$ 0 $ξ$), when $ξ$ $\ge$ 3, by providing a concrete finite antichain basis. We give a similar characterization for arbitrary relations when $ξ$ = 1. When $ξ$ = 2, we provide a concrete antichain of size continuum made of locally countable Borel relations minimal among non-$Σ$ 0 2 (or non-$Π$ 0 2) relations. The proof of this last result allows us to strengthen a result due to Baumgartner in topological Ramsey theory on the space of rational numbers. We prove that positive results hold when $ξ$ = 2 in the acyclic case. We give a general positive result in the non-necessarily locally countable case, with another suitable acyclicity assumption. We provide a concrete finite antichain basis for the class of uncountable analytic relations. Finally, we deduce from our positive results some antichain basis for graphs, of small cardinality (most of the time 1 or 2).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Acyclicity and reduction

The literature provides dichotomies involving homomorphisms (like the G 0 dichotomy) or reductions (like the characterization of sets potentially in a Wadge class of Borel sets, which holds on a subset of a product). However, part of the motivation behind the latter result was to get reductions on the whole product, like in the classical notion of Borel reducibility considered in the study of analytic equivalence relations. This is not possible in general. We show that, under some acyclicity (and also topological) assumptions, this is widely possible. In particular, we prove that, for any non-self dual Borel class Γ, there is a concrete finite =< c-antichain basis for the class of Borel relations, whose closure has acyclic symmetrization, and which are not potentially in Γ. Along similar lines, we provide a sufficient condition for =< c-reducing G 0. We also prove a similar result giving a minimum set instead of an antichain if we allow rectangular reductions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Upper Bound on the Complexity of Recognizable Tree Languages

The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $\Game (D\_n({\bfΣ}^0\_2))$ for some natural number $n\geq 1$, where $\Game$ is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space $2^ω$ into the class ${\bfΔ}^1\_2$, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ${\bfΔ}^1\_2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Universal and complete sets in martingale theory

The Doob convergence theorem implies that the set of divergence of any martingale has measure zero. We prove that, conversely, any $G\_{δσ}$ subset of the Cantor space with Lebesgue-measure zero can be represented as the set of divergence of some martingale. In fact, this is effective and uniform. A consequence of this is that the set of everywhere converging martingales is ${\bfΠ}^1\_1$-complete, in a uniform way. We derive from this some universal and complete sets for the whole projective hierarchy, via a general method. We provide some other complete sets for the classes ${\bfΠ}^1\_1$ and ${\bfΣ}^1\_2$ in the theory of martingales.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dichotomy Theorems for Families of Non-Cofinal Essential Complexity

We prove that for every Borel equivalence relation $E$, either $E$ is Borel reducible to $\mathbb{E}\_0$, or the family of Borel equivalence relations incompatible with $E$ has cofinal essential complexity. It follows that if $F$ is a Borel equivalence relation and $\cal F$ is a family of Borel equivalence relations of non-cofinal essential complexity which together satisfy the dichotomy that for every Borel equivalence relation $E$, either $E\in {\cal F}$ or $F$ is Borel reducible to $E$, then $\cal F$ consists solely of smooth equivalence relations, thus the dichotomy is equivalent to a known theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Essential countability of treeable equivalence relations

We establish a dichotomy theorem characterizing the circumstances under which a treeable Borel equivalence relation E is essentially countable. Under additional topological assumptions on the treeing, we in fact show that E is essentially countable if and only if there is no continuous embedding of E1 into E. Our techniques also yield the first classical proof of the analogous result for hypersmooth equivalence relations, and allow us to show that up to continuous Kakutani embeddability, there is a minimum Borel function which is not essentially countable-to-one.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Baire-class $ξ$ colorings: the first three levels

The $\mathbb{G}_0$-dichotomy due to Kechris, Solecki and Todor\vcević characterizes the analytic relations having a Borel-measurable countable coloring. We give a version of the $\mathbb{G}_0$-dichotomy for $\boraxi$-measurable countable colorings when $ξ\leq 3$. A $\boraxi$-measurable countable coloring gives a covering of the diagonal consisting of countably many $\boraxi$ squares. This leads to the study of countable unions of $\boraxi$ rectangles. We also give a Hurewicz-like dichotomy for such countable unions when $ξ\leq 2$.

0 citations0 reviewsNo code linkedOpen access