Publikation:

On Cluster Machines and Function Classes

Lade...
Vorschaubild

Dateien

Kosub_2-1snhrv1w4g34n9.pdf
Kosub_2-1snhrv1w4g34n9.pdfGröße: 154.25 KBDownloads: 51

Datum

1997

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Technical Reports, Institut für Informatik, Universität Würzburg; 172

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Working Paper/Technical Report
Publikationsstatus
Published

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)
004 Informatik

Schlagwörter

Complexity, Function classes

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690KOSUB, Sven, 1997. On Cluster Machines and Function Classes
BibTex
@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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt

Prüfdatum der URL

2021-12-10

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen