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 3

Displaying 41 – 51 of 51

Showing per page

Distance desert automata and the star height problem

Daniel Kirsten (2010)

RAIRO - Theoretical Informatics and Applications

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

Diversity in inside factorial monoids

Ulrich Krause, Jack Maney, Vadim Ponomarenko (2012)

Czechoslovak Mathematical Journal

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

Jack Maney, Vadim Ponomarenko (2012)

Czechoslovak Mathematical Journal

Let M be a (commutative cancellative) monoid. A nonunit element q ∈ M is called almost primary if for all a , b ∈ M , q ∣ a b implies that there exists k ∈ ℕ such that q ∣ a k or q ∣ b k . 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...

Currently displaying 41 – 51 of 51

Previous Page 3