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