Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Introduction to the Theory of Computation (view)

searching for theory of computation 193 found (442 total)

Rice's theorem (1,686 words) [view diff] no match in snippet view article find links to article

In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the

Avi Wigderson (837 words) [view diff] exact match in snippet view article find links to article

for his contributions to the understanding of randomness in the theory of computation. Avi Wigderson was born in Haifa, Israel, to Holocaust survivors

UTM theorem (242 words) [view diff] no match in snippet view article find links to article

In computability theory, the UTM theorem, or universal Turing machine theorem, is a basic result about Gödel numberings of the set of computable functions

David Deutsch (1,713 words) [view diff] exact match in snippet view article find links to article

Deutsch's universal quantum computer. ("The theory of computation is now the quantum theory of computation.") Richard Dawkins' refinement of Darwinian

Piotr Indyk (420 words) [view diff] case mismatch in snippet view article find links to article

Piotr Indyk is Thomas D. and Virginia W. Cabot Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory

Neil D. Jones (305 words) [view diff] exact match in snippet view article find links to article

Copenhagen. His work spanned both programming languages and the theory of computation. Within programming languages he was particularly known for his

Smn theorem (1,212 words) [view diff] no match in snippet view article find links to article

In computability theory the S m n theorem, written also as "smn-theorem" or "s-m-n theorem" (also called the translation lemma, parameter theorem, and

NSPACE (485 words) [view diff] case mismatch in snippet view article find links to article

Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2. Goddard, Wayne (2008). Introducing the Theory of Computation

International Journal of Algebra and Computation (91 words) [view diff] exact match in snippet view article find links to article

computational problems in algebra Theory of automata Formal language theory Theory of computation Theoretical computer science According to the Journal Citation Reports

PSPACE (981 words) [view diff] case mismatch in snippet view article find links to article

Zbl 1193.68112. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8.2–8.3 (The Class

Sierpiński space (1,908 words) [view diff] exact match in snippet view article find links to article

Sierpiński. The Sierpiński space has important relations to the theory of computation and semantics, because it is the classifying space for open sets

Rice–Shapiro theorem (2,355 words) [view diff] no match in snippet view article find links to article

In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, named after Henry Gordon Rice and Norman Shapiro. It states that

Chomsky normal form (1,924 words) [view diff] exact match in snippet view article find links to article

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

Faith Ellen (280 words) [view diff] exact match in snippet view article find links to article

the vice chair of SIGACT, the leading international society for theory of computation. From 2006 to 2009, she was chair of the steering committee for

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

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

P (complexity) (1,789 words) [view diff] case mismatch in snippet view article

1007/3-540-27477-4. ISBN 978-3-540-21045-0. Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3. Pocklington, H. C. (1910–1912)

R (complexity) (151 words) [view diff] exact match in snippet view article

co-RE. Blum, Lenore, Mike Shub, and Steve Smale, (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive

Ellipsoid method (3,656 words) [view diff] case mismatch in snippet view article find links to article

Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M. J. Atallah, CRC Press 1999, 31-1 to 31-37

Ronitt Rubinfeld (657 words) [view diff] case mismatch in snippet view article find links to article

Science at Tel Aviv University. At MIT she is a faculty lead for the Theory of Computation group at the Computer Science and Artificial Intelligence Laboratory

McCarthy 91 function (1,260 words) [view diff] case mismatch in snippet view article find links to article

f(n-1)} ). The example was popularized by Manna's book, Mathematical Theory of Computation (1974). As the field of Formal Methods advanced, this example appeared

Nondeterministic Turing machine (1,663 words) [view diff] case mismatch in snippet view article find links to article

"Section 4.6: Nondeterministic Turing machines". Elements of the Theory of Computation (1st ed.). Englewood Cliffs, New Jersey: Prentice-Hall. pp. 204–211

Alternating Turing machine (1,963 words) [view diff] case mismatch in snippet view article find links to article

(2006). Theory of Computation. Springer-Verlag. p. 58. ISBN 9781846282973. Michael Sipser (2006). Introduction to the Theory of Computation (2nd ed.)

McCarthy Formalism (1,133 words) [view diff] exact match in snippet view article find links to article

both as a programming language and as a vehicle for developing a theory of computation.... We shall need a number of mathematical ideas and notations concerning

Queue automaton (768 words) [view diff] case mismatch in snippet view article find links to article

Teodor. "Variants of Turing Machines" (PDF). Lecture Notes Covering Theory of Computation. University of Iowa, Iowa City, IA, 52242-1419. Archived from the

Spike response model (3,744 words) [view diff] exact match in snippet view article find links to article

response to step current input. The SRM has also been used in the theory of computation to quantify the capacity of spiking neural networks; and in the

Linear bounded automaton (816 words) [view diff] case mismatch in snippet view article find links to article

Automata slides, part of Context-sensitive Languages by Arthur C. Fleck Linear-Bounded Automata, part of Theory of Computation syllabus, by David Matuszek

Best-first search (505 words) [view diff] case mismatch in snippet view article find links to article

algorithms". In Atallah, Mikhail J. (ed.). Handbook of Algorithms and Theory of Computation. CRC Press. ISBN 0849326494. https://www.cs.cmu

NP (complexity) (2,771 words) [view diff] case mismatch in snippet view article

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

List of Jewish American computer scientists (1,638 words) [view diff] exact match in snippet view article find links to article

developed the idea of cut, copy, and paste Jeffrey Ullman, compilers, theory of computation, data-structures, databases, awarded Knuth Prize (2000) Peter J

Incompressibility method (3,534 words) [view diff] exact match in snippet view article find links to article

the incompressibility method with Kolmogorov complexity in the theory of computation was to prove that the running time of a one-tape Turing machine

Jim Hefferon (665 words) [view diff] case mismatch in snippet view article find links to article

inquiry-based Introduction to Proofs and a textbook on computer science, Theory of Computation. Hefferon is a member of the board of directors of the TeX Users

CYK algorithm (2,179 words) [view diff] exact match in snippet view article find links to article

p. 593-608, 1962. Sipser, Michael (2006). Introduction to the theory of computation (2nd ed.). Boston: Thomson Course Technology. Definition 2.8. ISBN 0-534-95097-3

L (complexity) (908 words) [view diff] case mismatch in snippet view article

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. 294–296

Lawrence Landweber (233 words) [view diff] case mismatch in snippet view article find links to article

is co-author of Brainerd, Walter S., and Lawrence H. Landweber. Theory of Computation. New York: Wiley, 1974. ISBN 978-0-471-09585-9. President, Internet

Carl Herbert Smith (143 words) [view diff] case mismatch in snippet view article find links to article

the author of the popular textbooks Theory of Computation: A Gentle Introduction and A Recursive Introduction to the Theory of Computation. v t e v t e

Baruch Schieber (835 words) [view diff] case mismatch in snippet view article find links to article

Vishkin. From 1987 to 1989 Schieber was a Postdoctoral Fellow at the Theory of Computation, Mathematical Sciences Department of IBM T.J. Watson Research Center

Quadratic growth (508 words) [view diff] case mismatch in snippet view article find links to article

order statistics", in Atallah, Mikhail J. (ed.), Algorithms and Theory of Computation Handbook, Boca Raton, Florida: CRC, pp. 3-1–3-25, MR 1797171. Griffeath

Silvio Micali (624 words) [view diff] case mismatch in snippet view article find links to article

from the original on 2019-12-05. Retrieved 2020-08-31. "MIT CSAIL Theory of Computation". theory.csail.mit.edu. Retrieved 2018-03-12. "Goldwasser, Micali

Context-sensitive language (1,340 words) [view diff] case mismatch 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.

Hamiltonian path problem (2,517 words) [view diff] case mismatch in snippet view article find links to article

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

EXPSPACE (681 words) [view diff] case mismatch in snippet view article find links to article

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

Chomsky hierarchy (1,310 words) [view diff] case mismatch in snippet view article find links to article

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

AC (complexity) (328 words) [view diff] case mismatch in snippet view article

Regan, Kenneth W. (1999), "Complexity classes", Algorithms and Theory of Computation Handbook, CRC Press. Vollmer, Heribert (1998), Introduction to circuit

Charles E. Leiserson (800 words) [view diff] case mismatch in snippet view article find links to article

Science and Artificial Intelligence Laboratory and principal of the Theory of Computation research group. He lists himself as Faculty Director of the MIT-Air

International Association for Cryptologic Research (1,420 words) [view diff] exact match in snippet view article find links to article

the practice of cryptography and secure systems as well as to the theory of computation at large. The needs of the theoretical cryptography (TC) community

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

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

Big O notation (8,286 words) [view diff] case mismatch in snippet view article find links to article

883. Mohr, Austin. "Quantum Computing in Complexity Theory and Theory of Computation" (PDF). p. 2. Archived (PDF) from the original on 8 March 2014.

Big O notation (8,286 words) [view diff] case mismatch in snippet view article find links to article

883. Mohr, Austin. "Quantum Computing in Complexity Theory and Theory of Computation" (PDF). p. 2. Archived (PDF) from the original on 8 March 2014.

PSPACE-complete (1,564 words) [view diff] case mismatch 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

3-opt (306 words) [view diff] exact match in snippet view article find links to article

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

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

Wainer 1970. Brainerd, Walter S.; Landweber, Lawrence H. (1974). Theory of computation. Wiley. ISBN 9780471095859. Cichon, E. A.; Wainer, S. S. (1983)

IP (complexity) (5,567 words) [view diff] case mismatch in snippet view article

for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp. 421–429. Shafi Goldwasser, Silvio Micali

NL (complexity) (1,290 words) [view diff] case mismatch in snippet view article

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 to

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

{\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ is prime}}\}} . In the theory of computation, these answers are represented as strings; for example, in the primality

Asymptote (disambiguation) (139 words) [view diff] exact match in snippet view article

describing limiting behaviour Asymptotic computational complexity, in theory of computation Asymptotic curve, a concept in differential geometry Asymptotology

Bernard Moret (462 words) [view diff] case mismatch in snippet view article find links to article

computational biology and bioinformatics. Moret is the author of The Theory of Computation (Addison-Wesley, 1998). With H. D. Shapiro, he is the co-author

Deterministic pushdown automaton (1,197 words) [view diff] case mismatch in snippet view article find links to article

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

Shortlex order (296 words) [view diff] case mismatch in snippet view article find links to article

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

State-transition table (772 words) [view diff] case mismatch 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

Mathematics Subject Classification (1,367 words) [view diff] exact match in snippet view article find links to article

Section 01) 53-04 Explicit machine computation and programs (not the theory of computation or programming) 53-06 Proceedings, conferences, collections, etc

Context-sensitive grammar (3,503 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-0-08-050246-5. Martin, John C. (2010). Introduction to Languages and the Theory of Computation (4th ed.). New York, NY: McGraw-Hill. p. 277. ISBN 9780073191461

Jennifer Wortman Vaughan (629 words) [view diff] case mismatch in snippet view article find links to article

Harvard University, where she was involved with the EconCS group, the Theory of Computation group, and the Center for Research on Computation and Society. Prior

Incompressible string (302 words) [view diff] case mismatch in snippet view article find links to article

Hence, this string is incompressible by our algorithm. V. Chandru and M.R.Rao, Algorithms and Theory of Computation Handbook, CRC Press 1999, p29-30.

Warren Sturgis McCulloch (1,148 words) [view diff] exact match in snippet view article find links to article

contribution to neural network theory, the theory of automata, the theory of computation, and cybernetics". McCulloch was the chair of the set of Macy conferences

*-algebra (1,359 words) [view diff] exact match in snippet view article find links to article

x* ∈ I and so on. *-rings are unrelated to star semirings in the theory of computation. A *-algebra A is a *-ring, with involution * that is an associative

Leonard Adleman (811 words) [view diff] exact match in snippet view article find links to article

of the National Academy of Engineering for contributions to the theory of computation and cryptography. He is also a member of the National Academy of

Time hierarchy theorem (2,467 words) [view diff] case mismatch in snippet view article find links to article

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

Log-space computable function (142 words) [view diff] case mismatch in snippet view article find links to article

International Second Edition, p. 328. Sipser, Michael (2006), Introduction to the Theory of Computation, Cengage Learning, ISBN 978-0-619-21764-8. v t e

Dynamic problem (algorithms) (418 words) [view diff] case mismatch in snippet view article

Z. Galil, and G. F. Italiano. "Dynamic graph algorithms". In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997. v t e

Context-free language (2,134 words) [view diff] case mismatch in snippet view article find links to article

McGraw-Hill. Sipser, Michael (1997). "2: Context-Free Languages". Introduction to the Theory of Computation. PWS Publishing. pp. 91–122. ISBN 0-534-94728-X.

Situation calculus (3,722 words) [view diff] case mismatch in snippet view article find links to article

completeness result for goal regression. Artificial and Mathematical Theory of Computation, 3. Lakemeyer, Gerhard. "The Situation Calculus and Golog: A Tutorial"

Reduction (complexity) (1,657 words) [view diff] case mismatch in snippet view article

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

Distribution learning theory (3,845 words) [view diff] exact match in snippet view article find links to article

basic definitions, tools and results in this framework from the theory of computation point of view. Let X {\displaystyle \textstyle X} be the support

Friedberg–Muchnik theorem (215 words) [view diff] case mismatch in snippet view article find links to article

Kozen, Dexter (2006). Lecture 38: The Friedberg–Muchnik Theorem. Theory of Computation. London: Springer. pp. 253–256. doi:10.1007/1-84628-477-5_48. Mučnik

Ryan Williams (computer scientist) (535 words) [view diff] case mismatch in snippet view article

at the Mathematics Genealogy Project "Ryan Williams | MIT CSAIL Theory of Computation". toc.csail.mit.edu. Retrieved 2021-12-18. Proceedings of 20th Annual

Andrew Yao (624 words) [view diff] exact match in snippet view article find links to article

science, "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation

Syntax (programming languages) (2,419 words) [view diff] case mismatch in snippet view article

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

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

989–996. Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, ISBN 1-55860-474-X

Syntax (programming languages) (2,419 words) [view diff] case mismatch in snippet view article

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

BlooP and FlooP (697 words) [view diff] case mismatch in snippet view article find links to article

University Press, p. 130. David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, Lecture 27. Hofstadter refers

Mikhail Atallah (535 words) [view diff] case mismatch in snippet view article find links to article

student Marina Blanton, Atallah is the editor of the Algorithms and Theory of Computation Handbook (CRC Press, 2nd ed., 2009, ISBN 978-1-58488-818-5). Atallah's

Simons Institute for the Theory of Computing (553 words) [view diff] exact match in snippet view article find links to article

insights gained from such explorations often reflect back to the theory of computation, opening new directions and advancing our understanding of fundamental

Formula game (234 words) [view diff] case mismatch 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

SL (complexity) (1,779 words) [view diff] case mismatch 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.

Stephen Smale (2,160 words) [view diff] exact match in snippet view article find links to article

MR 0228014. Blum, Lenore; Shub, Mike; Smale, Steve (1989). "On a theory of computation and complexity over the real numbers: NP-completeness, recursive

Cobham's thesis (684 words) [view diff] exact match in snippet view article find links to article

University Press, p. 128, ISBN 978-0-521-88473-0. Dexter Kozen (2006), Theory of computation, Birkhäuser, p. 4, ISBN 978-1-84628-297-3. Egon Börger (1989), Computability

Hao Wang (academic) (936 words) [view diff] case mismatch in snippet view article

1960a]. 50 Years of Computational Complexity: Hao Wang and the Theory of Computation, https://arxiv.org/abs/2206.05274 [Wang 1974 and 1985a] [Wang 1996a

Negligible function (1,167 words) [view diff] case mismatch in snippet view article find links to article

(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

Computation tree (293 words) [view diff] case mismatch in snippet view article find links to article

Elsevier, p. 595, ISBN 9780080533049. Moret, Bernard M. E. (1998), The Theory of Computation, Addison-Wesley, p. 338, ISBN 9780201258288. Ben-Or, M. (1983),

Christos Papadimitriou (980 words) [view diff] case mismatch in snippet view article find links to article

Prize of the Technion/Israel for the year 2018. Elements of the Theory of Computation (with Harry R. Lewis). Prentice-Hall, 1982; second edition September

Oracle machine (2,014 words) [view diff] exact match 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

Allan Borodin (465 words) [view diff] case mismatch in snippet view article find links to article

Algebraic and Numeric Problems. Elsevier Computer Science Library; Theory of Computation Series. Vol. 1. New York, London, Amsterdam: American Elsevier Publishing

Leslie Valiant (1,220 words) [view diff] exact match in snippet view article find links to article

M. Turing Award reads: For transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning

Jack Copeland (1,248 words) [view diff] case mismatch in snippet view article find links to article

technology". UK: Intute. Retrieved 7 December 2016. "History and Theory of Computation Sites". AlanTuring.net. Retrieved 4 January 2014. Westney, Lynn

Zohar Manna (397 words) [view diff] case mismatch in snippet view article find links to article

until retirement in 2010. He authored nine books. The Mathematical Theory of Computation (McGraw Hill, 1974; reprinted Dover, 2003) is one of the first texts

Real RAM (826 words) [view diff] exact match in snippet view article find links to article

S2CID 43787103. Blum, Lenore; Shub, Mike; Smale, Steve (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive

Government Engineering College, Ajmer (523 words) [view diff] case mismatch in snippet view article find links to article

Engineering, Operating Systems, Network Security, High Speed Networks, Theory of Computation, Mobile Computing, Design and Analysis of Algorithm and Data Mining

CXM (59 words) [view diff] exact match in snippet view article find links to article

CXM may refer to: Communicating X-Machine, in the field of the theory of computation Customer experience management IATA code of Camaxilo Airport, in

One-way function (1,880 words) [view diff] case mismatch in snippet view article find links to article

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.3: One-way

Banach fixed-point theorem (2,529 words) [view diff] case mismatch in snippet view article find links to article

Hitzler, Pascal (2010). "Generalized Distance Functions in the Theory of Computation". The Computer Journal. 53 (4): 443–464. doi:10.1093/comjnl/bxm108

Blum–Shub–Smale machine (628 words) [view diff] case mismatch in snippet view article find links to article

Real computer Blum, Lenore; Shub, Mike; Smale, Steve (1989). "On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive

Infinite loop (2,613 words) [view diff] case mismatch in snippet view article find links to article

computing .. a defect .. which .. to loop "Halting Problem in Theory of Computation". 3 October 2018. Archived from the original on 9 August 2020. Retrieved

BPP (complexity) (2,427 words) [view diff] case mismatch in snippet view article

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

Volgenau School of Engineering (873 words) [view diff] case mismatch in snippet view article find links to article

opportunities in many different areas including Algorithms and Theory of Computation, Artificial Intelligence and Robotics, Computer Vision, Computer

NP-completeness (3,618 words) [view diff] case mismatch 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. Papadimitriou

NP-completeness (3,618 words) [view diff] case mismatch 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. Papadimitriou

Affordance (3,029 words) [view diff] case mismatch in snippet view article find links to article

003. Wells, A. J. (July 2002). "Gibson's Affordances and Turing's Theory of Computation" (PDF). Ecological Psychology. 14 (3): 140–180. doi:10.1207/S15326969ECO1403_3

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

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

Alan Cobham (mathematician) (329 words) [view diff] case mismatch in snippet view article

Cobham: An Appreciation". Recursivity. Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3. Ausiello, Giorgio (2018)

Function composition (3,821 words) [view diff] case mismatch in snippet view article find links to article

79–80, 90–91. ISBN 978-1-4398-5129-6. Tourlakis, George (2012). Theory of Computation. John Wiley & Sons. p. 100. ISBN 978-1-118-31533-0. Lipscomb, S

Ron Rivest (1,533 words) [view diff] case mismatch in snippet view article find links to article

supervised by Robert W. Floyd. At MIT, Rivest is a member of the Theory of Computation Group, and founder of MIT CSAIL's Cryptography and Information Security

Hans-Joachim Bremermann (496 words) [view diff] exact match in snippet view article find links to article

mathematics and biophysics. By the 1960s, his work had turned towards the theory of computation and evolutionary biology, in which he studied complexity theory

Games, Puzzles, and Computation (548 words) [view diff] exact match in snippet view article find links to article

successful in its "purpose of building a bridge between games and the theory of computation". Leon Harkleroad is somewhat more critical, writing that the book

John McCarthy (computer scientist) (3,194 words) [view diff] exact match in snippet view article

ACM 3(4):184-195. McCarthy, J. 1963a "A basis for a mathematical theory of computation". In Computer Programming and formal systems. North-Holland. McCarthy

Nick Pippenger (415 words) [view diff] case mismatch in snippet view article find links to article

Dexter (2006). "Lecture 12: Relation of NC to Time-Space Classes". Theory of Computation. Springer. ISBN 978-1-84628-297-3. Pippinger, Nicholas (1976). "Formula

Lateral computing (4,212 words) [view diff] case mismatch in snippet view article find links to article

Edition. Harry R. Lewis, Christos H. Papadimtrou (1997); Elements of Theory of Computation, 2nd edition, Prentice Hall Publishers. M. Garey and D. Johnson

Raymond Reiter (341 words) [view diff] case mismatch in snippet view article find links to article

Vladimir Lifschitz, editor, Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, pages 359–380. Academic Press

Pumping lemma for context-free languages (1,526 words) [view diff] case mismatch in snippet view article find links to article

ISBN 0201003732. OCLC 783543642. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 1.4: Nonregular Languages

Berlekamp's algorithm (1,759 words) [view diff] case mismatch in snippet view article find links to article

finite field and irreducibility tests Cantor–Zassenhaus algorithm Theory of Computation - Dexter Kozen. Springer. Retrieved 2020-09-19. Berlekamp, Elwyn

Denotational semantics (3,769 words) [view diff] exact match in snippet view article find links to article

verification, and model checking. Dana S. Scott. Outline of a mathematical theory of computation. Technical Monograph PRG-2, Oxford University Computing Laboratory

NC (complexity) (2,434 words) [view diff] case mismatch in snippet view article

of algorithms. Lectures 28 - 34 and 36 Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. Springer-Verlag. ISBN 1-84628-297-7

Circuit complexity (2,565 words) [view diff] exact match in snippet view article find links to article

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

PCP theorem (1,751 words) [view diff] case mismatch in snippet view article find links to article

(PDF) (Draft). Cambridge University Press. Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. London: Springer-Verlag. pp. 119–127

GenoCAD (1,325 words) [view diff] case mismatch 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. ISBN 978-1-133-18779-0

Time complexity (5,004 words) [view diff] case mismatch 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, Kurt; Naher

Interactive proof system (2,720 words) [view diff] case mismatch 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: Interactive

Lenore Blum (1,481 words) [view diff] exact match in snippet view article find links to article

BSS. Blum, Lenore; Shub, Mike; Smale, Steve (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions

Operational semantics (2,561 words) [view diff] case mismatch in snippet view article find links to article

60-61:3-15, 2004. (preprint). Dana S. Scott. Outline of a Mathematical Theory of Computation, Programming Research Group, Technical Monograph PRG–2, Oxford University

Regular expression (8,916 words) [view diff] case mismatch in snippet view article find links to article

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

D. P. Sharma (1,178 words) [view diff] case mismatch in snippet view article find links to article

Technology(Print), ISBN 978-81-9054-83-4-2, Vol-2, August 2009, p. 282 Theory of Computation(Print), ISBN 978-81-9054-91-2-7, Vol-3, August 2012, p. 250 Sharma

Victor Pan (759 words) [view diff] exact match in snippet view article find links to article

American Mathematical Society, for "contributions to the mathematical theory of computation". Victor Pan at the Mathematics Genealogy Project Victor Pan of

Error correction code (4,679 words) [view diff] case mismatch in snippet view article find links to article

29th Annual Association for Computing Machinery (ACM) Symposium on Theory of Computation. "Digital Video Broadcast (DVB); Second generation framing structure

Harvey Prize (200 words) [view diff] exact match in snippet view article find links to article

quasi-periodic crystals. 1995 Donald E. Knuth U.S. Contributions to theory of computation, software, programming languages, mathematics and typesetting, his

Turochamp (2,102 words) [view diff] case mismatch in snippet view article find links to article

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 (2014)

Fermat pseudoprime (2,179 words) [view diff] exact match in snippet view article find links to article

In Atallah, Mikhail J.; Blanton, Marina (eds.). Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10–23.

Courant Institute of Mathematical Sciences (4,419 words) [view diff] exact match in snippet view article find links to article

offered in many areas such as natural language processing, the theory of computation, computer vision, software engineering, compiler optimization techniques

Las Vegas algorithm (2,547 words) [view diff] case mismatch in snippet view article find links to article

cmu.edu (PowerPoint). Retrieved 3 November 2018. Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999. "Las Vegas algorithm", in Dictionary

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

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

Madhan Karky (3,877 words) [view diff] exact match in snippet view article find links to article

In that particular stint, he developed a project based on the theory of computation and strong mathematics (under the supervision of Dr. George Havas)

Neurophilosophy (5,783 words) [view diff] exact match in snippet view article find links to article

and Pylyshyn require some sort of syntactic constraint on their theory of computation. This is consistent with their rejection of connectionist systems

History of computer science (5,439 words) [view diff] exact match in snippet view article find links to article

Lifschitz, Vladimir (1991). Artificial intelligence and mathematical theory of computation : papers in honor of John McCarthy. Academic Press. ISBN 0-12-450010-2

Kyoto Prize in Advanced Technology (557 words) [view diff] case mismatch in snippet view article find links to article

Andrew Chi-Chih Yao China born 1946 Pioneering Contributions to a New Theory of Computation and Communication and a Fundamental Theory for its Security.

Log-space transducer (398 words) [view diff] case mismatch in snippet view article find links to article

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

Eduardo D. Sontag (1,176 words) [view diff] exact match in snippet view article find links to article

with David Angeli the concept of input/output monotone system. In theory of computation, he proved the first results on computational complexity in nonlinear

Mary O'Kane (1,089 words) [view diff] case mismatch in snippet view article find links to article

received a Lectureship appointment in Artificial Intelligence and Theory of Computation at the Canberra College of Advanced Education, and was Dean of the

Boolean satisfiability problem (5,312 words) [view diff] case mismatch in snippet view article find links to article

Dexter C. (2006). "Supplementary Lecture F: Unique Satisfiability". Theory of Computation. Texts in Computer Science. Springer. p. 180. ISBN 9781846282973

Weird machine (726 words) [view diff] case mismatch in snippet view article find links to article

"Exploit Programming - From Buffer Overflows to "Weird Machines" and Theory of Computation" (PDF). ;login:. 36 (6): 13–21. Bratus, Sergey; Darley, Trey; Locasto

Michael Shub (878 words) [view diff] exact match in snippet view article find links to article

Blum, Lenore; Shub, Michael; Smale, Stephen (July 1989). "On a theory of computation and complexity over the real numbers: NP-completeness, recursive

Konrad Zuse (4,532 words) [view diff] exact match in snippet view article find links to article

dessen Anwendung auf Relaisschaltungen" [Inception of a universal theory of computation with special consideration of the propositional calculus and its

Cook–Levin theorem (2,358 words) [view diff] case mismatch in snippet view article find links to article

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 NP). Now suppose

Specified complexity (3,883 words) [view diff] case mismatch in snippet view article find links to article

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

Christopher Cherniak (1,597 words) [view diff] exact match in snippet view article find links to article

other. A next chapter of this research program: Concepts from the theory of computation can be applied to understand the structure and function of organisms'

Ruy de Queiroz (1,250 words) [view diff] case mismatch in snippet view article find links to article

Solomon Feferman), Logic for Computer Science, Discrete Mathematics, Theory of Computation, Proof Theory, Model Theory, Foundations of Cryptography. He has

Jelani Nelson (1,270 words) [view diff] exact match in snippet view article find links to article

Bradley C. Kuszmaul and Charles E. Leiserson. He was a member of the theory of computation group, working on efficient algorithms for massive datasets. His

Bhavani Thuraisingham (357 words) [view diff] exact match in snippet view article find links to article

Minnesota in 1977 and 1984 respectively. She earned a Ph.D. in the theory of computation and computability theory from the University of Wales, Swansea in

Kolmogorov complexity (7,143 words) [view diff] case mismatch in snippet view article find links to article

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

Oblivious transfer (1,967 words) [view diff] case mismatch in snippet view article find links to article

Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988. Paper at ACM portal (subscription required) Giovanni

Two-way finite automaton (1,619 words) [view diff] case mismatch in snippet view article find links to article

0114. This definition has been taken from lecture notes of CS682 (Theory of Computation) by Dexter Kozen of Stanford University Kapoutsis, Christos (2005)

Binary logarithm (4,788 words) [view diff] case mismatch 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. Sedgewick

Issa Al-Ghaith (214 words) [view diff] case mismatch in snippet view article find links to article

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

Cristina Sernadas (342 words) [view diff] case mismatch in snippet view article find links to article

Press, 1999; 2nd ed., 2004; 3rd ed., 2014) Foundations of Logic and Theory of Computation (with A. Sernadas, College Publications, 2008; 2nd ed., 2012) Analysis

Context-free grammar (6,129 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-0321210296. Sipser, Michael (1997), Introduction to the Theory of Computation, PWS Publishing, ISBN 978-0-534-94728-6. Chapter 2: Context-Free

Space hierarchy theorem (2,699 words) [view diff] case mismatch in snippet view article find links to article

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

Addition (9,560 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-0-387-95448-6. Martin, John (2003). Introduction to Languages and the Theory of Computation (3 ed.). McGraw-Hill. ISBN 978-0-07-232200-2. Riehl, Emily (2016)

Radiation therapy (13,529 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-1-4200-3453-0. Atallah MJ, Blanton M (20 November 2009). Algorithms and Theory of Computation Handbook, Volume 2: Special Topics and Techniques. CRC Press. p

Noam Chomsky (18,414 words) [view diff] case mismatch in snippet view article find links to article

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

Code as data (716 words) [view diff] case mismatch in snippet view article find links to article

Panangaden, Prakash. "Notes on the recursion theorem" (PDF). COMP 330 Theory of Computation. McGill University. Retrieved 15 January 2023. Bohme, Rainer; Moore

Logic (16,841 words) [view diff] case mismatch in snippet view article find links to article

Publishing Company. ISBN 978-0-8284-0238-5. Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Benjamin/Cummings Pub

Philosophy of mind (11,040 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-0-262-13417-0. Sipser, M. (1998). Introduction to the Theory of Computation. Boston, Mass.: PWS Publishing Co. ISBN 978-0-534-94728-6. Searle

Plankalkül (2,735 words) [view diff] exact match in snippet view article find links to article

dessen Anwendung auf Relaisschaltungen [Inception of a universal theory of computation with special consideration of the propositional calculus and its

Frame problem (4,821 words) [view diff] case mismatch in snippet view article find links to article

Lifschitz, Vladimir (ed.). Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy. New York: Academic Press. pp

Generalized geography (1,908 words) [view diff] case mismatch 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.

Logic programming (10,723 words) [view diff] case mismatch in snippet view article find links to article

completeness result for goal regression. Artificial and Mathematical Theory of Computation, 3. Merritt, D., 2012. Building expert systems in Prolog. Springer

Algorithm characterizations (8,851 words) [view diff] case mismatch in snippet view article find links to article

three texts. Lewis, H.R. and Papadimitriou, C.H. Elements of the Theory of Computation, Prentice-Hall, Uppre Saddle River, N.J., 1998 A. A. Markov (1954)

General semantics (6,819 words) [view diff] exact match in snippet view article find links to article

(verbal testimony) is Paul Vitanyi (born 1944), a scientist in the theory of computation.[citation needed] During the 1940s, 1950s, and 1960s, general semantics

True quantified Boolean formula (3,764 words) [view diff] case mismatch in snippet view article find links to article

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

Proof of knowledge (1,635 words) [view diff] case mismatch in snippet view article find links to article

interactive proof-systems. Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Draft. Extended abstract Mihir

Turing scheme (1,159 words) [view diff] case mismatch in snippet view article find links to article

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

Probabilistic context-free grammar (5,256 words) [view diff] case mismatch in snippet view article find links to article

PMC 3350620. PMID 22495308. Sipser M. (1996). Introduction to Theory of Computation. Brooks Cole Pub Co. Michael A. Harrison (1978). Introduction to

Jean Salençon (878 words) [view diff] exact match in snippet view article find links to article

viscoelasticity and their industrial applications. He is the author of the theory of computation at break which he implemented for the first global computation of

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

Conference on Unconventional Models of Computation in 1998. The general theory of computation allows for a variety of methods of computation. Computing technology

History of computing in the Soviet Union (6,455 words) [view diff] case mismatch in snippet view article find links to article

November 2017. Lifschitz, Vladimir (2012). Artificial and Mathematical Theory of Computation: Papers in Honor of John McCarthy. Academic Press. pp. 299–300.

List of University of California, Berkeley faculty (15,278 words) [view diff] exact match in snippet view article find links to article

(2000) "in recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation

Information algebra (2,296 words) [view diff] exact match in snippet view article find links to article

ISBN 978-1-118-01086-0 Scott, Dana S. (1970), Outline of a mathematical theory of computation, Technical Monograph PRG–2, Oxford University Computing Laboratory

Event calculus (3,138 words) [view diff] exact match in snippet view article find links to article

Vladimir Lifshitz, editor, Artificial intelligence and mathematical theory of computation: papers in honour of John McCarthy, pages 359–380, San Diego, CA

Diamond norm (782 words) [view diff] case mismatch in snippet view article find links to article

Mixed States". Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computation (STOC). pp. 20–30. arXiv:quant-ph/9806029. J. Watrous. The Theory

Glossary of engineering: A–L (31,767 words) [view diff] exact match in snippet view article find links to article

communicate digital information. A computer scientist specializes in the theory of computation and the design of computational systems. Concave lens Lenses are

Yale shooting problem (1,200 words) [view diff] case mismatch in snippet view article find links to article

Vladimir Lifschitz, editor, Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, pages 359–380. Academic Press

Perceptrons (book) (5,191 words) [view diff] exact match in snippet view article

linear threshold modules. This does not in any sense reduce the theory of computation and programming to the theory of perceptrons." Hu, Sze-Tsen. Threshold

Rainbow Honor Walk (13,347 words) [view diff] case mismatch in snippet view article find links to article

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

List of University of Texas at Dallas people (2,492 words) [view diff] case mismatch in snippet view article find links to article

Science from the University of Minnesota in 1984, a Ph.D. in the Theory of Computation and Computability Theory from the University of Wales in 1979, and

Legacy of Alan Turing (5,714 words) [view diff] exact match in snippet view article find links to article

Istanbul Bilgi University organises an annual conference on the theory of computation called "Turing Days". The University of Texas at Austin has an honours

List of fellows of IEEE Computer Society (104 words) [view diff] exact match in snippet view article find links to article

distributed systems. 1992 John Savage For contributions to the theory of computation and design and analysis of VLSI algorithms. 1993 Jacob Savir For