206

206

9 March 2017 - 14h00

Deterministic Automaton and logically definable sets of numbers.

by Arthur Milchior from Université Paris Diderot IRIF

Abstract: For a fixed base b, any integer can be encoded as a finite word of

alphabet of digits. In dimension d>0, a vector of d integers is encoded

as a word of alphabet of vector of d digits. A set of vector of integers

is thus encoded as a language whose alphabet is the set of vector of

digits. Thus, an automaton whose alphabet is the set of vector of digits

recognizes a set of integers. Similarly, a Büchi automaton recognizes a

set of vector of real.

It is then natural to consider algorithms which decide whether the set

of vectors of numbers accepted by a finite automaton admits some

properties. For example, Honkala proved in 1986 that it is decidable

whether an automaton recognize a FO[N,+,<]-definable set of integers.

Muchnik proved a similar result for automata recognizing sets of vectors

of integers. A polynomial-time algorithm was then given by Leroux in

2006, and a quasi-linear time algorithm for the case of dimension 1 was

given in 2013 by Marsault and Sakarovitch.

We state that it is decidable in linear time:

- whether a set of reals recognized by a given finite minimal weak Büchi

automaton is FO[R,+,<]-definable.

- whether a set of vectors recognized by a minimal finite deterministic

automaton can be defined in some logics less expressive than FO[N,+],

such as FO[N,<,mod].

Furthermore, formulas which defines those sets can be computed in linear

time and cubic time respectively.

Furthermore, is shown that it is decidable whether a set of vector of

real or of integers accepted by a (weak Büchi) automaton:

- is definable in a logic which admits quantifier-elimination. For

example, if the set is definable in FO[R,+,<], FO[R,Z,+,<,mod,floor]

where mod is the set of modular predicate, FO[N,<,mod] or FO[<].

- satisfies a first-order formula in some formalism. For example, whether

a set is a submonoid/subsemigroup of (R^d,+)

In this talk, I intend to:

- introduce automata recognizing set of vector of numbers,

- characterize the set of numbers which are FO[N,<,mod]- and

FO[R,+,<]-definable,

- introduce and generalizes the methods used by Honkala, Muchnik and

Marsault-Sakarovitch

- explain how how those methods can be applied to the above-mentioned

problems.