Displaying similar documents to “Non literal tranducers and some problems of normality”

The entropy of Łukasiewicz-languages

Ludwig Staiger (2005)

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

Similarity:

The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.

Residuality of dynamical morphisms

R. Burton, M. Keane, Jacek Serafin (2000)

Colloquium Mathematicae

Similarity:

We present a unified approach to the finite generator theorem of Krieger, the homomorphism theorem of Sinai and the isomorphism theorem of Ornstein. We show that in a suitable space of measures those measures which define isomorphisms or respectively homomorphisms form residual subsets.

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2010)

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

Similarity:

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some ℓ additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with ℓ nested pebbles....