Displaying similar documents to “Rational tree morphisms and transducer integer sequences: definition and examples.”

Complexity of testing morphic primitivity

Štěpán Holub, Vojtěch Matocha (2013)

Kybernetika

Similarity:

We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in 𝒪 ( m · n ) , where n is the length of the word and m the size of the alphabet.

Factor frequencies in generalized Thue-Morse words

Ľubomíra Balková (2012)

Kybernetika

Similarity:

We describe factor frequencies of the generalized Thue-Morse word 𝐭 b , m defined for b ≥ 2 , m ≥ 1 , b , m ∈ ℕ , as the fixed point starting in 0 of the morphism ϕ b , m ( k ) = k ( k + 1 ) ⋯ ( k + b - 1 ) , where k ∈ { 0 , 1 , ⋯ , m - 1 } and where the letters are expressed modulo m . We use the result of Frid [4] and the study of generalized Thue-Morse words by Starosta [6].

Automata with modulo counters and nondeterministic counter bounds

Daniel Reidenbach, Markus L. Schmid (2014)

Kybernetika

Similarity:

We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way multi-head automata that comprise a constant number of modulo counters, where the counter bounds are nondeterministically guessed, and this is the only element of nondeterminism. NBMCA are tailored to recognising those languages that are characterised by the existence of a specific factorisation of their words, e. g., pattern languages. In this work, we subject NBMCA to a theoretically...