5 papers
A Quasi-Linear Time Algorithm Deciding Whether Weak Büchi Automata Reading Vectors of Reals Recognize Saturated Languages
Arthur Milchior
This work considers weak deterministic Büchi automata reading encodings of non-negative -vectors of reals in a fixed base. A saturated language is a language which contains all…
(Quasi-)linear time algorithm to compute LexDFS, LexUP and LexDown orderings
Arthur Milchior
We consider the three graph search algorithm LexDFS, LexUP and LexDOWN. We show that LexUP orderings can be computed in linear time by an algorithm similar to the one which compute…
Uniform definition of sets using relations and complement of Presburger Arithmetic
Arthur Milchior
In 1996, Michaux and Villemaire considered integer relations which are not definable in Presburger Arithmetic. That is, not definable in first-order logic over integers with th…
Büchi automata recognizing sets of reals definable in first-order logic with addition and order
Arthur Milchior
This work considers weak deterministic Büchi automata reading encodings of non-negative reals in a fixed base. A Real Number Automaton is an automaton which recognizes all encoding…
A Note on Higher Order and Variable Order Logic over Finite Models
Arthur Milchior
We show that descriptive complexity's result extends in High Order Logic to capture the expressivity of Turing Machine which have a finite number of alternation and whose time or s…