Displaying 21 – 40 of 51

Showing per page

Differences in sets of lengths of Krull monoids with finite class group

Wolfgang A. Schmid (2005)

Journal de Théorie des Nombres de Bordeaux

Let H be a Krull monoid with finite class group where every class contains some prime divisor. It is known that every set of lengths is an almost arithmetical multiprogression. We investigate which integers occur as differences of these progressions. In particular, we obtain upper bounds for the size of these differences. Then, we apply these results to show that, apart from one known exception, two elementary p -groups have the same system of sets of lengths if and only if they are isomorphic.

Distance desert automata and the star height problem

Daniel Kirsten (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 2 2 𝒪 ( 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 bound...

Currently displaying 21 – 40 of 51