Displaying similar documents to “Regularity of languages defined by formal series with isolated cut point∗”

Regularity of languages defined by formal series with isolated cut point

Alberto Bertoni, Maria Paola Bianchi, Flavi D’Alessandro (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let  = { ∈  | ()  } be the language recognized by a formal series :  → ℝ with isolated cut point . We provide new conditions that guarantee the regularity of the language in the case that is rational or is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.

Regularity of languages defined by formal series with isolated cut point

Alberto Bertoni, Maria Paola Bianchi, Flavi D’Alessandro (2012)

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

Similarity:

Let  = { ∈  | ()  } be the language recognized by a formal series :  → ℝ with isolated cut point . We provide new conditions that guarantee the regularity of the language in the case that is rational or is a Hadamard quotient of rational series. Moreover the decidability property of such conditions is investigated.

Closure properties of hyper-minimized automata

Andrzej Szepietowski (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 for a language finitely different from . In this paper we show...

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...

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and...

Integers in number systems with positive and negative quadratic Pisot base

Z. Masáková, T. Vávra (2014)

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

Similarity:

We consider numeration systems with base and − , for quadratic Pisot numbers and focus on comparing the combinatorial structure of the sets Z and Z of numbers with integer expansion in base , resp. − . Our main result is the comparison of languages of infinite words and coding the ordering of distances between consecutive - and (− )-integers. It turns out that for a class of roots of − − , the languages coincide, while for other...

Substitution systems associated with the dynamical system (𝒜, )

Maria de Fátima Correia, Carlos Ramos, Sandra Vinagre (2012)

ESAIM: Proceedings

Similarity:

We consider the dynamical system (𝒜, ), where 𝒜 is a class of differential real functions defined on some interval and : 𝒜 → 𝒜 is an operator := , where is a differentiable -modal map. If we consider functions in 𝒜 whose critical values are periodic points for then, we show how to define and characterize a substitution system associated with (𝒜, ...

Linear size test sets for certain commutative languages

Štěpán Holub, Juha Kortelainen (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that for each positive integer the finite commutative language = ( ...) possesses a test set of size at most Moreover, it is shown that each test set for has at least -1 elements. The result is then generalized to commutative languages containing a word such that (i) alph() = alph}(); and (ii) each symbol ∈ alph}() occurs at least twice in if it occurs at least twice in some word of : each such possesses...

Pointwise constrained radially increasing minimizers in the quasi-scalar calculus of variations

Luís Balsa Bicho, António Ornelas (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We prove of vector minimizers () =  (||) to multiple integrals ∫ ((), |()|)  on a  ⊂ ℝ, among the Sobolev functions (·) in + (, ℝ), using a  : ℝ×ℝ → [0,∞] with (·) and . Besides such basic hypotheses, (·,·) is assumed to satisfy also...

One-Rule Length-Preserving Rewrite Systems and Rational Transductions

Michel Latteux, Yves Roos (2014)

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

Similarity:

We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side and the right-hand side of the rule of the system are not quasi-conjugate or are equal, that means if and are distinct, there do not exist words , and such that  =  and  = . We prove...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...