On multiplicatively dependent 
linear numeration systems, 
and periodic points

Christiane Frougny

Displaying similar documents to “On multiplicatively dependent linear numeration systems, and periodic points”

Computing the Rabin Index of a Parity Automaton

Olivier Carton, Ramón Maceiras (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The Rabin index of a rational language of infinite words given by a parity automaton with states is computable in time ( ) where is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This...

Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that the size of a automaton and the size of a complete, minimal automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction to , but here...

Periodic stabilization for linear time-periodic ordinary differential equations

Gengsheng Wang, Yashan Xu (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

This paper studies the periodic feedback stabilization of the controlled linear time-periodic ordinary differential equation: () = ()() + ()(), ≥ 0, where [(·)(·)] is a -periodic pair, , (·) ∈ (ℝ; ℝ) and (·) ∈ (ℝ; ℝ) satisfy respectively ( + ) = () for a.e. ≥ 0 and ( + ) = () for a.e. ≥ 0. Two periodic stablization criteria for a -period pair [(·)(·)] are established. One is an analytic criterion which is related to the transformation over time associated...

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton...

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Forbidden Factors and Fragment Assembly

F. Mignosi, A. Restivo, M. Sciortino (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word from a given set of substrings () of a word . We introduce an hypothesis involving the set of fragments and the maximal length of the minimal forbidden factors of . Such hypothesis allows us to reconstruct uniquely the word from the set in linear time....

On Conjugacy of Languages

Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We say that two languages and are conjugates if they satisfy the for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.