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 9 Next

Displaying 161 – 180 of 186

Showing per page

The globals of pseudovarieties of ordered semigroups containing B2 and an application to a problem proposed by Pin

Jorge Almeida, Ana P. Escada (2010)

RAIRO - Theoretical Informatics and Applications

Given a basis of pseudoidentities for a pseudovariety of ordered semigroups containing the 5-element aperiodic Brandt semigroup B2, under the natural order, it is shown that the same basis, over the most general graph over which it can be read, defines the global. This is used to show that the global of the pseudovariety of level 3/2 of Straubing-Thérien's concatenation hierarchy has infinite vertex rank.

The lattice of varieties of fibered automata

Anna Mućka (2006)

Discussiones Mathematicae - General Algebra and Applications

The class of all fibered automata is a variety of two-sorted algebras. This paper provides a full description of the lattice of varieties of fibred automata.

The pseudovariety of semigroups of triangular matrices over a finite field

Jorge Almeida, Stuart W. Margolis, Mikhail V. Volkov (2005)

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

We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.

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

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

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

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

RAIRO - Theoretical Informatics and Applications

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

Tree transformations defined by hypersubstitutions

Sr. Arworn, Klaus Denecke (2001)

Discussiones Mathematicae - General Algebra and Applications

Tree transducers are systems which transform trees into trees just as automata transform strings into strings. They produce transformations, i.e. sets consisting of pairs of trees where the first components are trees belonging to a first language and the second components belong to a second language. In this paper we consider hypersubstitutions, i.e. mappings which map operation symbols of the first language into terms of the second one and tree transformations defined by such hypersubstitutions....

Currently displaying 161 – 180 of 186