Showing 2017Show all
2 papers · 1 filter
cs.FL2017
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…
cs.DS2017
(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…