Page 1 Next

Displaying 1 – 20 of 75

Showing per page

The completely distributive lattice of machine invariant sets of infinite words

Aleksandrs Belovs, Jānis Buls (2007)

Discussiones Mathematicae - General Algebra and Applications

We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.

The cyclicity problem for the images of Q-rational series

Juha Honkala (2011)

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

We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.

The cyclicity problem for the images of Q-rational series

Juha Honkala (2012)

RAIRO - Theoretical Informatics and Applications

We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.

The entropy of Łukasiewicz-languages

Ludwig Staiger (2005)

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

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.

The entropy of Łukasiewicz-languages

Ludwig Staiger (2010)

RAIRO - Theoretical Informatics and Applications

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.

The factor automaton

Milan Šimánek (2002)

Kybernetika

This paper concerns searching substrings in a string using the factor automaton. The factor automaton is a deterministic finite automaton constructed to accept every substring of the given string. Nondeterministic factor automaton is used to achieve new operations on factor automata for searching in non-constant texts.

The finite automata approaches in stringology

Jan Holub (2012)

Kybernetika

We present an overview of four approaches of the finite automata use in stringology: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions. We also show how the finite automata can process strings build over more complex alphabet than just single symbols (degenerate symbols, strings, variables).

Currently displaying 1 – 20 of 75

Page 1 Next