### Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. (Unter Benutzung nachgelassener Sätze von K. Hentzelt)

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

Promise problems have been introduced in 1985 by S. Even e.a. as a generalization of decision problems. Using a very general approach we study solvability and unsolvability conditions for promise problems of set and language families. We show, that cores of unsolvability are completely determined by partitions of cohesive sets. We prove the existence of cores in unsolvable promise problems assuming certain closure properties for the given set family. Connections to immune sets and complexity cores...

We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.

**Page 1**