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

Olivier Finkel

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

ResearcherUnclaimed source record
Logic in Computer Sciencemath.LOComputational ComplexityFormal Languages and Automata TheoryComputer Science and Game TheoryDiscrete Mathematicsmath.GN

Catalog footprint

What is connected

21works
7topics
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

21 published item(s)

preprint2022arXiv

On Bi-infinite and Conjugate Post Correspondence Problems

We study two modifications of the Post Correspondence Problem (PCP), namely 1) the bi-infinite version, where it is asked whether there exists a bi-infinite word such that two given morphisms agree on it, and 2) the conjugate version, where we require the images of a solution for two given morphisms are conjugates of each other. For the bi-infinite PCP we show that it is in the class $Σ_2^0$ of the arithmetical hierarchy and for the conjugate PCP we give an undecidability proof by reducing it to the word problem for a special type of semi-Thue systems.

0 citations0 reviewsNo code linkedOpen access
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
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
preprint2014arXiv

Ambiguity of ω-Languages of Turing Machines

An ω-language is a set of infinite words over a finite alphabet X. We consider the class of recursive ω-languages, i.e. the class of ω-languages accepted by Turing machines with a Büchi acceptance condition, which is also the class Σ11 of (effective) analytic subsets of Xω for some finite alphabet X. We investigate here the notion of ambiguity for recursive ω-languages with regard to acceptance by Büchi Turing machines. We first present in detail essentials on the literature on ω-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of Büchi Turing machines and of the ω-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Infinite Games Specified by 2-Tape Automata

We prove that the determinacy of Gale-Stewart games whose winning sets are infinitary rational relations accepted by 2-tape Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. Then we prove that winning strategies, when they exist, can be very complex, i.e. highly non-effective, in these games. We prove the same results for Gale-Stewart games with winning sets accepted by real-time 1-counter Büchi automata, then extending previous results obtained about these games. Then we consider the strenghs of determinacy for these games, and we prove that there is a transfinite sequence of 2-tape Büchi automata (respectively, of real-time 1-counter Büchi automata) $A_α$, indexed by recursive ordinals, such that the games $G(L(A_α))$ have strictly increasing strenghs of determinacy. Moreover there is a 2-tape Büchi automaton (respectively, a real-time 1-counter Büchi automaton) B such that the determinacy of G(L(B)) is equivalent to the (effective) analytic determinacy and thus has the maximal strength of determinacy. We show also that the determinacy of Wadge games between two players in charge of infinitary rational relations accepted by 2-tape Büchi automata is equivalent to the (effective) analytic determinacy, and thus not provable in ZFC.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Determinacy of Context-Free Games

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B)).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Topological Complexity of Context-Free omega-Languages: A Survey

We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-deterministic or deterministic context-free omega-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of omega-powers.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Automatic Ordinals

We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $ω^{ω^ω}$. Then we show that the injectively $ω^n$-automatic ordinals, where $n>0$ is an integer, are the ordinals smaller than $ω^{ω^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11] the subclasses of finite word $ω^n$-automatic ordinals. As a by-product we obtain that the hierarchy of injectively $ω^n$-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Hierarchy of Tree-Automatic Structures

We consider $ω^n$-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length $ω^n$ for some integer $n\geq 1$. We show that all these structures are $ω$-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for $ω^2$-automatic (resp. $ω^n$-automatic for $n>2$) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for $ω^n$-automatic boolean algebras, $n > 1$, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a $Σ_2^1$-set nor a $Π_2^1$-set. We obtain that there exist infinitely many $ω^n$-automatic, hence also $ω$-tree-automatic, atomless boolean algebras $B_n$, $n\geq 1$, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [FT10].

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Borel Hierarchy and Omega Context Free Languages

We give in this paper additional answers to questions of Lescow and Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994), 583-621], proving new topological properties of omega context free languages : there exist some omega-CFL which are non Borel sets. And one cannot decide whether an omega-CFL is a Borel set. We give also an answer to questions of Niwinski and Simonnet about omega powers of finitary languages, giving an example of a finitary context free language L such that L^omega is not a Borel set. Then we prove some recursive analogues to preceding properties: in particular one cannot decide whether an omega-CFL is an arithmetical set.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Decision Problems for Recognizable Languages of Infinite Pictures

Altenbernd, Thomas and Wöhrle have considered in [ATW02] acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. Many classical decision problems are studied in formal language theory and in automata theory and arise now naturally about recognizable languages of infinite pictures. We first review in this paper some recent results of [Fin09b] where we gave the exact degree of numerous undecidable problems for Büchi-recognizable languages of infinite pictures, which are actually located at the first or at the second level of the analytical hierarchy, and "highly undecidable". Then we prove here some more (high) undecidability results. We first show that it is $Π_2^1$-complete to determine whether a given Büchi-recognizable languages of infinite pictures is unambiguous. Then we investigate cardinality problems. Using recent results of [FL09], we prove that it is $D_2(Σ_1^1)$-complete to determine whether a given Büchi-recognizable language of infinite pictures is countably infinite, and that it is $Σ_1^1$-complete to determine whether a given Büchi-recognizable language of infinite pictures is uncountable. Next we consider complements of recognizable languages of infinite pictures. Using some results of Set Theory, we show that the cardinality of the complement of a Büchi-recognizable language of infinite pictures may depend on the model of the axiomatic system ZFC. We prove that the problem to determine whether the complement of a given Büchi-recognizable language of infinite pictures is countable (respectively, uncountable) is in the class $Σ_3^1 \setminus (Π_2^1 \cup Σ_2^1)$ (respectively, in the class $Π_3^1 \setminus (Π_2^1 \cup Σ_2^1)$).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Some Problems in Automata Theory Which Depend on the Models of Set Theory

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an omega-language $L(A)$ accepted by a Büchi 1-counter automaton $A$. We prove the following surprising result: there exists a 1-counter Büchi automaton $A$ such that the cardinality of the complement $L(A)^-$ of the omega-language $L(A)$ is not determined by ZFC: (1). There is a model $V_1$ of ZFC in which $L(A)^-$ is countable. (2). There is a model $V_2$ of ZFC in which $L(A)^-$ has cardinal $2^{\aleph_0}$. (3). There is a model $V_3$ of ZFC in which $L(A)^-$ has cardinal $\aleph_1$ with $\aleph_0<\aleph_1<2^{\aleph_0}$. We prove a very similar result for the complement of an infinitary rational relation accepted by a 2-tape Büchi automaton $B$. As a corollary, this proves that the Continuum Hypothesis may be not satisfied for complements of 1-counter omega-languages and for complements of infinitary rational relations accepted by 2-tape Büchi automata. We infer from the proof of the above results that basic decision problems about 1-counter omega-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem to determine whether the complement of a 1-counter omega-language (respectively, infinitary rational relation) is countable is in $Σ_3^1 \setminus (Π_2^1 \cup Σ_2^1)$. This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Determinacy of Context-Free Games

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B)).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language

It was noticed by Harel in [Har86] that "one can define $Σ_1^1$-complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular $ω$-language is $Σ_1^1$-complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is $Π_1^1$-complete to determine whether two given infinitary rational relations are disjoint. Then we prove that there is an amazing gap between two decision problems about $ω$-rational functions realized by finite state Büchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given $ω$-rational function is continuous, while we show here that it is $Σ_1^1$-complete to determine whether a given $ω$-rational function has at least one point of continuity. Next we prove that it is $Π_1^1$-complete to determine whether the continuity set of a given $ω$-rational function is $ω$-regular. This gives the exact complexity of two problems which were shown to be undecidable in [CFS08].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Isomorphism Relation Between Tree-Automatic Structures

An $ω$-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for $ω$-tree-automatic structures. We prove first that the isomorphism relation for $ω$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is not determined by the axiomatic system ZFC. Then we prove that the isomorphism problem for $ω$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is neither a $Σ_2^1$-set nor a $Π_2^1$-set.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

On Decidability Properties of One-Dimensional Cellular Automata

In a recent paper Sutner proved that the first-order theory of the phase-space $\mathcal{S}_\mathcal{A}=(Q^\mathbb{Z}, \longrightarrow)$ of a one-dimensional cellular automaton $\mathcal{A}$ whose configurations are elements of $Q^\mathbb{Z}$, for a finite set of states $Q$, and where $\longrightarrow$ is the "next configuration relation", is decidable. He asked whether this result could be extended to a more expressive logic. We prove in this paper that this is actuallly the case. We first show that, for each one-dimensional cellular automaton $\mathcal{A}$, the phase-space $\mathcal{S}_\mathcal{A}$ is an omega-automatic structure. Then, applying recent results of Kuske and Lohrey on omega-automatic structures, it follows that the first-order theory, extended with some counting and cardinality quantifiers, of the structure $\mathcal{S}_\mathcal{A}$, is decidable. We give some examples of new decidable properties for one-dimensional cellular automata. In the case of surjective cellular automata, some more efficient algorithms can be deduced from results of Kuske and Lohrey on structures of bounded degree. On the other hand we show that the case of cellular automata give new results on automatic graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

On Some Sets of Dictionaries Whose omega-Powers Have a Given Complexity

A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [Omega-powers and descriptive set theory, JSL 2005] the complexity of the set of dictionaries whose associated omega-powers have a given complexity. In particular, he considered the sets $W({\bf\Si}^0_{k})$ (respectively, $W({\bfΠ}^0_{k})$, $W({\bfΔ}_1^1)$) of dictionaries $V \subseteq 2^\star$ whose omega-powers are ${\bf\Si}^0_{k}$-sets (respectively, ${\bfΠ}^0_{k}$-sets, Borel sets). In this paper we first establish a new relation between the sets $W({\bfΣ}^0_{2})$ and $W({\bfΔ}_1^1)$, showing that the set $W({\bfΔ}_1^1)$ is "more complex" than the set $W({\bfΣ}^0_{2})$. As an application we improve the lower bound on the complexity of $W({\bfΔ}_1^1)$ given by Lecomte. Then we prove that, for every integer $k\geq 2$, (respectively, $k\geq 3$) the set of dictionaries $W({\bfΠ}^0_{k+1})$ (respectively, $W({\bf\Si}^0_{k+1})$) is "more complex" than the set of dictionaries $W({\bfΠ}^0_{k})$ (respectively, $W({\bf\Si}^0_{k})$) .

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The Complexity of Infinite Computations In Models of Set Theory

We prove the following surprising result: there exist a 1-counter Büchi automaton and a 2-tape Büchi automaton such that the ω-language of the first and the infinitary rational relation of the second in one model of ZFC are π_2^0-sets, while in a different model of ZFC both are analytic but non Borel sets. This shows that the topological complexity of an ω-language accepted by a 1-counter Büchi automaton or of an infinitary rational relation accepted by a 2-tape Büchi automaton is not determined by the axiomatic system ZFC. We show that a similar result holds for the class of languages of infinite pictures which are recognized by Büchi tiling systems. We infer from the proof of the above results an improvement of the lower bound of some decision problems recently studied by the author.

0 citations0 reviewsNo code linkedOpen access