Find link

language:

Find link is a tool written by Edward Betts.

searching for Introduction to the Theory of Computation 74 found (94 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 (745 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

PSPACE (982 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

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

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

3-opt (306 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

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

Context-sensitive language (1,340 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.

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,348 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

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

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

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

Time hierarchy theorem (2,497 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

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

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

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,658 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

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

Oracle machine (2,028 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

Syntax (programming languages) (2,436 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

Negligible function (1,680 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

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

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

BPP (complexity) (2,455 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

One-way function (1,956 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

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

Big O notation (9,104 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

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:

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,102 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

Time complexity (5,003 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,

Algorithm (6,907 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

Finite-state machine (4,528 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.

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

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

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.

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

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,157 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

Regular expression (8,860 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,356 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,784 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

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

Kolmogorov complexity (7,565 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

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)

Turing machine (9,420 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

Alan Turing (15,046 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

Lateral computing (4,212 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

Noam Chomsky (18,636 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

Philosophy of mind (12,162 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

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,481 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,483 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,410 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