About: Alternating Turing machine

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Alternating Turing machine Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

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.

Attributes	Values
rdf:type	software
rdfs:label	Alternating Turing machine (en)
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. (en)
sameAs	Alternating Turing machine Alternating Turing machine
dbp:wikiPageUsesTemplate	dbt:Citation_needed dbt:Cite_book dbt:More_footnotes dbt:Mvar dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Null dbt:Turing
Subject	Models of computation
Link from a Wikipage to an external page	https://books.google.com/books%3Fid=wR_oBwAAQBAJ%7Cyear
gold:hypernym	Machine
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Alternating_Turing_machine?oldid=1072613732&ns=0
Wikipage page ID	753230 (xsd:integer)
page length (characters) of wiki page	12424 (xsd:nonNegativeInteger)
Wikipage revision ID	1072613732 (xsd:integer)
Link from a Wikipage to another Wikipage	Formal language Logic optimization NP-completeness Nondeterministic Turing machine Ashok K. Chandra Boolean function Boolean satisfiability problem Tuple Models of computation PSPACE P (complexity) True quantified Boolean formula Co-NP Complexity class Algorithmic complexity Constructible function EXPSPACE EXPTIME Parallel computation thesis Immerman–Szelepcsényi theorem Dexter Kozen LH (complexity) Larry Stockmeyer Polynomial hierarchy
has 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Alternating_Turing_machine
is Wikipage redirect of	Alternating turing machine Alternation (complexity) Existential state Alternating computation Universal state (Turing)
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures List of things named after Alan Turing NC (complexity) NSPACE NTIME 2-EXPTIME AC (complexity) ATM Alternating turing machine Alternation Alternation (complexity) Ashok K. Chandra Atime Double exponential function Turing machine DTIME Algorithmic complexity EXPTIME List of complexity classes List of computability and complexity topics Immerman–Szelepcsényi theorem Exponential hierarchy LH (complexity) Larry Stockmeyer Multitape Turing machine Existential state Alternating computation
is known for of	Ashok K. Chandra
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Alternating_Turing_machine

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 881 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software