Decidability of equational theories of coverings of semigroup varieties.
Decidability of periodicity for infinite words
Decompositions of semigroups induced by identities.
Definability in the lattice of equational theories of semigroups.
Direct products of cyclic semigroups admitting a planar Cayley graph.
Disjunctive languages and compatible orders
Disjunctive splittability of languages.
Distance desert automata and the star height problem
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in space whether the language accepted by an -state non-deterministic automaton is of a star height less than a given integer (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound...
Distance desert automata and the star height problem
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...
Distributive groupoids and biassociativity.
Distributive groupoids and biassociativity. (Short Communication).
Diversity in inside factorial monoids
In a recent paper (Diversity in Monoids, Czech. Math. J. 62 (2012), 795–809), the last two authors introduced and developed the monoid invariant “diversity” and related properties “homogeneity” and “strong homogeneity”. We investigate these properties within the context of inside factorial monoids, in which the diversity of an element counts the number of its different almost primary components. Inside factorial monoids are characterized via diversity and strong homogeneity. A new invariant complementary...
Diversity in monoids
Let be a (commutative cancellative) monoid. A nonunit element is called almost primary if for all , implies that there exists such that or . We introduce a new monoid invariant, diversity, which generalizes this almost primary property. This invariant is developed and contextualized with other monoid invariants. It naturally leads to two additional properties (homogeneity and strong homogeneity) that measure how far an almost primary element is from being primary. Finally, as an application...