Technical Report TR-1996-15

BibliographyHertrampf, Ulrich: Acceptance by Transformation Monoids (with an Application to Local Self Reductions).
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1996/15.
24 pages, english.
CR-SchemaF.1.3 (Complexity Classes)
KeywordsKomplexitätsklasse; Monoid
Abstract

We study the power of transformation monoids, which are used as an acceptance mechanism of nondeterministic polynomial time machines. Focussing our attention on four types of transformation monoids (including the monoids of all transformations on k elements) we obtain exact characterizations of all investigated polynomial time classes.

We apply these results to the cases of locally self reducible sets and of bottleneck Turing machines to obtain complete solutions to the formerly open problems related to these models. Especially, the complexity of k-locally self reducible sets for all numbers k, as well as the complexity of width-3 or width-4 bottleneck Turing machines are determined completely. Also for m-k-locally self reducible sets (i.e. k-locally self reducible sets, where the self reduction is given by a many-one reduction function) we determine the complexity exactly for all k.

Full text and
other links
HTML (generated from PostScript)
Department(s)University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
Entry dateJanuary 28, 1997
   Publ. Computer Science