All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 45

Showing per page

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

Let Lϕ,λ = {ω ∈ Σ∗ | ϕ(ω) > λ} be the language recognized by a formal series ϕ:Σ∗ → ℝ with isolated cut point λ. We provide new conditions that guarantee the regularity of the language Lϕ,λ 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

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

Relating automata-theoretic hierarchies to complexity-theoretic hierarchies

Victor L. Selivanov (2002)

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

We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

Victor L. Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

Relative goodness of EOL forms

H. A. Maurer, A. Salomaa, D. Wood (1978)

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

Representations of a free group of rank two by time-varying Mealy automata

Adam Woryna (2005)

Discussiones Mathematicae - General Algebra and Applications

In the group theory various representations of free groups are used. A representation of a free group of rank two by the so-calledtime-varying Mealy automata over the changing alphabet is given. Two different constructions of such automata are presented.

Currently displaying 21 – 40 of 45