Find link

Introduction to the Theory of Computation not in Time complexity

language:

Find link is a tool written by Edward Betts.

searching for Introduction to the Theory of Computation 75 found (95 total)

alternate case: introduction to the Theory of Computation

Algorithms Unlocked (67 words) [view diff] case mismatch in snippet view article find links to article

fundamentals of cryptography and data compression, and an introduction to the theory of computation. "Algorithms Unlocked". MIT Press. Retrieved December

Carl Herbert Smith (166 words) [view diff] exact match in snippet view article find links to article

of Computation: A Gentle Introduction and A Recursive Introduction to the Theory of Computation. He died of brain cancer in 2004. "Carl H. Smith (1950-2004)"

Recursive language (771 words) [view diff] exact match in snippet view article find links to article

1016/0022-0000(78)90021-1. Sipser, Michael (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.

NSPACE (485 words) [view diff] exact match in snippet view article find links to article

usefulness to real-world applications. Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2

Chomsky normal form (1,926 words) [view diff] case mismatch in snippet view article find links to article

from the original on 2021-07-19. Sipser, Michael (2006). Introduction to the theory of computation (2nd ed.). Boston: Thomson Course Technology. Definition

Post correspondence problem (2,521 words) [view diff] exact match in snippet view article find links to article

following discussion is based on Michael Sipser's textbook Introduction to the Theory of Computation. In more detail, the idea is that the string along the

EXPSPACE (648 words) [view diff] exact match in snippet view article find links to article

doi:10.1016/0304-3975(80)90037-7. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 9.1.1: Exponential

PSPACE (998 words) [view diff] exact match in snippet view article find links to article

Polynomial space, pp. 455–490. Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. ISBN 0-534-95097-3

CYK algorithm (2,189 words) [view diff] case mismatch in snippet view article find links to article

Office, London, p. 593-608, 1962. Sipser, Michael (2006). Introduction to the theory of computation (2nd ed.). Boston: Thomson Course Technology. Definition

Multitape Turing machine (543 words) [view diff] exact match in snippet view article find links to article

machine Turing machine equivalents Sipser, Michael (2005). Introduction to the Theory of Computation. Thomson Course Technology. p. 148. ISBN 0-534-95097-3

Unambiguous Turing machine (380 words) [view diff] exact match in snippet view article find links to article

1016/0020-0190(76)90097-1. Sipser, Michael (1996-12-01). Introduction to the Theory of Computation (1st ed.). International Thomson Publishing. ISBN 978-0-534-94728-6

NP (complexity) (2,784 words) [view diff] exact match in snippet view article

is described by many textbooks, for example, Sipser's Introduction to the Theory of Computation, section 7.3. To show this, first, suppose we have a deterministic

St-connectivity (518 words) [view diff] exact match in snippet view article find links to article

P-complete (Immerman 1999, p. 54). Sipser, Michael (2006), Introduction to the Theory of Computation, Thompson Course Technology, ISBN 0-534-95097-3 Immerman

Shortlex order (298 words) [view diff] exact match in snippet view article find links to article

lexicographic order Level order Sipser, Michael (2012). Introduction to the Theory of Computation (3 ed.). Boston, MA: Cengage Learning. p. 14. ISBN 978-1133187790

L (complexity) (1,503 words) [view diff] exact match in snippet view article

395–408. ISBN 0-201-53082-1. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. Section 8.4: The Classes L and NL, pp

Decision problem (1,246 words) [view diff] exact match in snippet view article find links to article

MIT Press. ISBN 978-0-262-68052-3. Sipser, M. (2020). Introduction to the Theory of Computation. Cengage Learning. ISBN 978-0-357-67058-3. Soare, Robert

Chomsky hierarchy (1,346 words) [view diff] exact match in snippet view article find links to article

Wiley and Sons, Inc. pp. 323–418. Sipser, Michael (1997). Introduction to the Theory of Computation (1st ed.). Cengage Learning. p. 130. ISBN 0-534-94728-X

PSPACE-complete (1,564 words) [view diff] exact match in snippet view article find links to article

Sipser, Michael (1997), "Section 8.3: PSPACE-completeness", Introduction to the Theory of Computation, PWS Publishing, pp. 283–294, ISBN 0-534-94728-X

Deterministic pushdown automaton (1,236 words) [view diff] exact match in snippet view article find links to article

PDA, equivalence is undecidable. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. p. 102. ISBN 0-534-94728-X. Soltys-kulinicz

State-transition table (781 words) [view diff] exact match in snippet view article find links to article

CiteSeerX 10.1.1.72.8657, doi:10.1109/32.317428 Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X

Formula game (234 words) [view diff] exact match in snippet view article find links to article

true, no matter what choice Player A makes. Sipser, Michael. (2006). Introduction to the Theory of Computation. Boston: Thomson Course Technology. v t e

Time hierarchy theorem (2,511 words) [view diff] exact match in snippet view article find links to article

ISBN 0-7695-2228-9. S2CID 5555450. Sipser, Michael (27 June 2012). Introduction to the Theory of Computation (3rd ed.). CENGAGE learning. ISBN 978-1-133-18779-0. Sudborough

P (complexity) (1,940 words) [view diff] exact match in snippet view article

Addison–Wesley. ISBN 978-0-201-53082-7. Sipser, Michael (2006). Introduction to the Theory of Computation, 2nd Edition. Course Technology Inc. ISBN 978-0-534-95097-2

Context-sensitive language (1,457 words) [view diff] exact match in snippet view article find links to article

doi:10.1137/0217058. Archived (PDF) from the original on 2004-06-25. Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

Syntax (programming languages) (1,886 words) [view diff] exact match in snippet view article

ISBN 0-201-65697-3. Michael Sipser (1997). "2.2 Pushdown Automata". Introduction to the Theory of Computation. PWS Publishing. pp. 101–114. ISBN 0-534-94728-X. LtU

Emptiness problem (210 words) [view diff] exact match in snippet view article find links to article

Intersection non-emptiness problem Sipser, Michael (2012). Introduction to the Theory of Computation. Cengage Learning. ISBN 9781285401065. "Lecture 6: Properties

Alternating Turing machine (2,010 words) [view diff] exact match in snippet view article find links to article

Springer-Verlag. p. 58. ISBN 9781846282973. Michael Sipser (2006). Introduction to the Theory of Computation (2nd ed.). PWS Publishing. ISBN 978-0-534-95097-2. Section

Reduction (complexity) (1,661 words) [view diff] exact match in snippet view article

problem to a decidable one. As Michael Sipser points out in Introduction to the Theory of Computation: "The reduction must be easy, relative to the complexity

NL (complexity) (1,570 words) [view diff] exact match in snippet view article

The Classes L and NL, NL-completeness, NL equals coNL". Introduction to the Theory of Computation. PWS Publishing. pp. 294–302. ISBN 0-534-94728-X. Introduction

Savitch's theorem (1,094 words) [view diff] exact match in snippet view article find links to article

Sipser, Michael (1997), "Section 8.1: Savitch's Theorem", Introduction to the Theory of Computation, PWS Publishing, pp. 279–281, ISBN 0-534-94728-X Lance

SL (complexity) (1,793 words) [view diff] exact match in snippet view article

Addison-Wesley, 1994. ISBN 0-201-53082-1. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.

Generalized nondeterministic finite automaton (496 words) [view diff] exact match in snippet view article find links to article

pp. 156–166. doi:10.1007/b105090 Michael Sipser. 2006. Introduction to the Theory of Computation (2nd ed.). International Thomson Publishing. A graphical

Negligible function (1,679 words) [view diff] exact match in snippet view article find links to article

Michael (1997). "Section 10.6.3: One-way functions". Introduction to the Theory of Computation. PWS Publishing. pp. 374–376. ISBN 0-534-94728-X. Papadimitriou

Powerset construction (1,500 words) [view diff] exact match in snippet view article find links to article

ISSN 0018-8646. Sipser, Michael (1997). "Theorem 1.19". Introduction to the Theory of Computation. pp. 55–56. ISBN 0-534-94728-X. Hopcroft, John E.; Ullman

Oracle machine (2,046 words) [view diff] case mismatch in snippet view article find links to article

McGraw-Hill. OCLC 559483934. Sipser, Michael (1997). Introduction to the theory of computation. Boston: PWS Publishing. ISBN 978-0-534-94728-6. OCLC 300459879

GenoCAD (1,325 words) [view diff] exact match in snippet view article find links to article

PMC 2748682. PMID 19816554. Sipser, Michael (2013). Introduction to the Theory of Computation, Third edition. Boston, MA, USA: Cengage Learning. p. 104

Enumerator (computer science) (565 words) [view diff] exact match in snippet view article

halt, thus rejecting the string. Sipser, Michael (2012). Introduction to the Theory of Computation - International Edition. Cengage Learning. ISBN 978-1-133-18781-3

One-way function (1,951 words) [view diff] exact match in snippet view article find links to article

CRC Press. ISBN 1-58488-551-3. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Section 10.6

BPP (complexity) (2,456 words) [view diff] exact match in snippet view article

section 11.4: Circuit complexity. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 10.2.1: The

Pumping lemma for context-free languages (1,532 words) [view diff] exact match in snippet view article find links to article

/ Date incompatibility (help) Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 1.4: Nonregular

3-opt (612 words) [view diff] case mismatch in snippet view article find links to article

1287/opre.21.2.498. ISSN 0030-364X. Sipser, Michael (2006). Introduction to the theory of computation. Boston: Thomson Course Technology. ISBN 0-534-95097-3

Computability (3,293 words) [view diff] exact match in snippet view article find links to article

complexity theory Computability logic Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Part Two: Computability

Gadget (computer science) (1,604 words) [view diff] exact match in snippet view article

hdl:10338.dmlcz/101241, MR 0063008. Sipser, Michael (1997), Introduction to the Theory of Computation, PWS Publishing Co., p. 260. This reduction is described

Interactive proof system (2,746 words) [view diff] exact match in snippet view article find links to article

University Press, March 2009. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Section 10.4:

Big O notation (9,101 words) [view diff] exact match in snippet view article find links to article

Leipzig: B.G. Teubner. p. 31. Sipser, Michael (1997). Introduction to the Theory of Computation. Boston, MA: PWS Publishing. p. 227, def. 7.2. Cormen

NP-completeness (3,618 words) [view diff] exact match in snippet view article find links to article

(NP-completeness, Additional NP-complete Problems)". Introduction to the Theory of Computation. PWS Publishing. pp. 248–271. ISBN 978-0-534-94728-6.

Circuit complexity (2,571 words) [view diff] case mismatch in snippet view article find links to article

Circuit minimization See proof. Sipser, Michael (1997). Introduction to the theory of computation (1 ed.). Boston, USA: PWS Publishing Company. p. 324.

Turochamp (2,106 words) [view diff] exact match in snippet view article find links to article

Press. ISBN 978-4-87187-801-2. Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-95097-2. Dasgupta, Subrata

Hamiltonian path problem (2,518 words) [view diff] exact match in snippet view article find links to article

problem at Wikimedia Commons Sipser, Michael (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. pp. 292–314. Garey, Michael

Issa Al-Ghaith (288 words) [view diff] exact match in snippet view article find links to article

Saudi Arabia in Transition – Bernard Haykel،Thomas . Introduction to the Theory of Computation – Michael Sipser. 500 Most Powerful Muslims Archived 1

Algorithm (7,016 words) [view diff] exact match in snippet view article find links to article

Publishers/Elsevier. ISBN 978-0-12-374514-9. Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company. ISBN 978-0-534-94728-6. Sober

Cook–Levin theorem (2,354 words) [view diff] exact match in snippet view article find links to article

can be found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3., as well as in the Wikipedia article on

Finite-state machine (4,529 words) [view diff] exact match in snippet view article find links to article

Bartlett. ISBN 978-0-7637-3834-1. Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Boston Mass: Thomson Course Technology.

Log-space reduction (1,358 words) [view diff] exact match in snippet view article find links to article

Springer Press. ISBN 3-540-58355-6. Sipser, Michael (2012). Introduction to the Theory of Computation. Cengage Learning. ISBN 978-0-619-21764-8. v t e

Time complexity (4,997 words) [view diff] exact match in snippet view article find links to article

L-notation Space complexity Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2. Mehlhorn,

Generalized geography (1,908 words) [view diff] exact match in snippet view article find links to article

Theoretical Computer Science. 112 (2): 371–381. doi:10.1016/0304-3975(93)90026-p. Michael Sipser, Introduction to the Theory of Computation, PWS, 1997.

Specified complexity (3,965 words) [view diff] exact match in snippet view article find links to article

Wayback Machine (loc. cit. p. 16) Michael Sipser (1997). Introduction to the Theory of Computation, PWS Publishing Company. Lloyd, Seth (2002-05-24). "Computational

Turing scheme (1,161 words) [view diff] exact match in snippet view article find links to article

481–485. ISBN 978-0-12-386980-7. Sipser, Michael (2012). Introduction to the Theory of Computation. Cengage Learning. ISBN 9781285401065. Turing scheme website

Space hierarchy theorem (2,784 words) [view diff] exact match in snippet view article find links to article

171-187. February 24, 2003. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages 306–310 of

Regular expression (8,871 words) [view diff] exact match in snippet view article find links to article

Sipser, Michael (1998). "Chapter 1: Regular Languages". Introduction to the Theory of Computation. PWS Publishing. pp. 31–90. ISBN 978-0-534-94728-6. Stubblebine

Halting problem (7,350 words) [view diff] exact match in snippet view article find links to article

Michael (2006). "Section 4.2: The Halting Problem". Introduction to the Theory of Computation (Second ed.). PWS Publishing. pp. 173–182. ISBN 0-534-94728-X

P versus NP problem (7,797 words) [view diff] exact match in snippet view article find links to article

Theoretical Computer Science. 38: 101–107. Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson

Alan Turing (15,054 words) [view diff] exact match in snippet view article find links to article

1945 (2.6 ed.). Wynne Press. Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-95097-2. Turing, A. M

Binary logarithm (5,128 words) [view diff] exact match in snippet view article find links to article

ISBN 978-1-4200-9983-6. Sipser, Michael (2012), "Example 7.4", Introduction to the Theory of Computation (3rd ed.), Cengage Learning, pp. 277–278, ISBN 9781133187790

Turing machine (9,384 words) [view diff] exact match in snippet view article find links to article

1967, ISBN 0-262-68052-1 (pbk.) Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 3: The Church–Turing

True quantified Boolean formula (3,846 words) [view diff] exact match in snippet view article find links to article

Complexity. Reading: Addison-Wesley. Sipser, Michael. (2006). Introduction to the Theory of Computation. Boston: Thomson Course Technology. Zhang, Lintao. (2003)

Kolmogorov complexity (7,896 words) [view diff] exact match in snippet view article find links to article

Springer-Verlag. ISBN 978-0-7204-2844-5. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS. ISBN 0-534-95097-3. Downey, Rodney G.; Hirschfeldt

Lateral computing (4,213 words) [view diff] exact match in snippet view article find links to article

H. Freeman and Company Publishers. M. Sipser (2001); Introduction to the Theory of Computation, Thomson/Brooks/Cole Publishers. K. Compton and S. Hauck

Philosophy of mind (12,407 words) [view diff] exact match in snippet view article find links to article

1233119. PMC 10435742. PMID 37600559. Sipser, M. (1998). Introduction to the Theory of Computation. Boston, Mass.: PWS Publishing Co. ISBN 978-0-534-94728-6

Noam Chomsky (18,676 words) [view diff] exact match in snippet view article find links to article

Wiley-Blackwell. ISBN 0-631-20891-7. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6 – via Internet

Complexity class (10,382 words) [view diff] exact match in snippet view article find links to article

original on January 21, 2022. Sipser, Michael (2006). Introduction to the Theory of Computation (PDF) (2nd ed.). USA: Thomson Course Technology. ISBN 0-534-95097-3

Glossary of artificial intelligence (29,514 words) [view diff] exact match in snippet view article find links to article

0:47 / 2:17 from YouTube clip Sipser, Michael (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. central

Algorithm characterizations (8,991 words) [view diff] exact match in snippet view article find links to article

Université Sorbonne Paris Nord, [1]. Sipser, Michael, (2006), Introduction to the Theory of Computation: Second Edition, Thompson Course Technology div. of Thompson

Mathematics education in the United States (12,778 words) [view diff] exact match in snippet view article find links to article

Wiley-Interscience. ISBN 978-0-471-24195-9. Sipser, Michael (1996). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. ISBN 978-1-133-18779-0. Cormen

Rainbow Honor Walk (13,413 words) [view diff] exact match in snippet view article find links to article

location missing publisher (link) Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-95097-2. Todd, Pamela