Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

Cohesiveness in promise problems

Ulrike BrandtHermann K.-G. Walter — 2013

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Weightreducing grammars and ultralinear languages

Ulrike BrandtGhislain DelepineHermann K.-G. Walter — 2004

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Weightreducing grammars and ultralinear languages

Ulrike BrandtGhislain DelepineHermann K.-G. Walter — 2010

RAIRO - Theoretical Informatics and Applications

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

Download Results (CSV)