Publikation: On Cluster Machines and Function Classes
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
We consider a special kind of non-deterministic Turing machines. Cluster machines are distinguished by a neighbourhood relationship between accepting paths. Based on a for- malization using equivalence relations some subtle properties of these machines are proven. Moreover, by abstraction we gain the machine-independend concept of cluster sets which is the starting point to establish cluster operators. Cluster operators map complexity classes of sets into complexity classes of functions where for the domain classes only cluster sets are allowed. For the counting operator c# and the optimization operators cmax and cmin the structural relationships between images resulting from these operators on the polynomial-time hierarchy are investigated. Furthermore, we compare cluster operators with the corresponding common operators # , max and min [Tod90b, HW97].
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
KOSUB, Sven, 1997. On Cluster Machines and Function ClassesBibTex
@techreport{Kosub1997Clust-55840, year={1997}, series={Technical Reports, Institut für Informatik, Universität Würzburg}, title={On Cluster Machines and Function Classes}, number={172}, url={http://www1.pub.informatik.uni-wuerzburg.de/pub/TRs/kosub97.ps.gz}, author={Kosub, Sven} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/55840"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:title>On Cluster Machines and Function Classes</dcterms:title> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-10T14:29:22Z</dcterms:available> <dc:contributor>Kosub, Sven</dc:contributor> <dc:rights>terms-of-use</dc:rights> <dcterms:abstract xml:lang="eng">We consider a special kind of non-deterministic Turing machines. Cluster machines are distinguished by a neighbourhood relationship between accepting paths. Based on a for- malization using equivalence relations some subtle properties of these machines are proven. Moreover, by abstraction we gain the machine-independend concept of cluster sets which is the starting point to establish cluster operators. Cluster operators map complexity classes of sets into complexity classes of functions where for the domain classes only cluster sets are allowed. For the counting operator c# and the optimization operators cmax and cmin the structural relationships between images resulting from these operators on the polynomial-time hierarchy are investigated. Furthermore, we compare cluster operators with the corresponding common operators # , max and min [Tod90b, HW97].</dcterms:abstract> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/55840/3/Kosub_2-1snhrv1w4g34n9.pdf"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/55840"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/55840/3/Kosub_2-1snhrv1w4g34n9.pdf"/> <dc:creator>Kosub, Sven</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-10T14:29:22Z</dc:date> <dc:language>eng</dc:language> <dcterms:issued>1997</dcterms:issued> </rdf:Description> </rdf:RDF>