This HTML5 document contains 47 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15https://books.google.com/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n12http://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Alternating_Turing_machine
rdf:type
dbo:Software
rdfs:label
Alternating Turing machine
rdfs:comment
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981.
owl:sameAs
yago-res:Alternating_Turing_machine freebase:m.038ft3
dbp:wikiPageUsesTemplate
dbt:Null dbt:More_footnotes dbt:Short_description dbt:Citation_needed dbt:Unreferenced_section dbt:Turing dbt:Cite_book dbt:Reflist dbt:Mvar
dct:subject
dbc:Models_of_computation
dbo:wikiPageExternalLink
n15:books%3Fid=wR_oBwAAQBAJ%7Cyear
gold:hypernym
dbr:Machine
prov:wasDerivedFrom
n12:Alternating_Turing_machine?oldid=1072613732&ns=0
dbo:wikiPageID
753230
dbo:wikiPageLength
12424
dbo:wikiPageRevisionID
1072613732
dbo:wikiPageWikiLink
dbr:Parallel_computation_thesis dbr:EXPSPACE dbr:Complexity_class dbc:Models_of_computation dbr:Logic_optimization dbr:Computational_complexity_theory dbr:Larry_Stockmeyer dbr:P_(complexity) dbr:Polynomial_hierarchy dbr:Boolean_satisfiability_problem dbr:Immerman–Szelepcsényi_theorem dbr:True_quantified_Boolean_formula dbr:PSPACE dbr:Dexter_Kozen dbr:NP_(complexity) dbr:Constructible_function dbr:LH_(complexity) dbr:Ashok_K._Chandra dbr:Tuple dbr:Formal_language dbr:Boolean_function dbr:Nondeterministic_Turing_machine dbr:Co-NP dbr:EXPTIME
dbo:abstract
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981.
foaf:isPrimaryTopicOf
n12:Alternating_Turing_machine