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 195 found (447 total)

Rice's theorem (1,712 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

Piotr Indyk (445 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

David Deutsch (1,884 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

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

Avi Wigderson (1,004 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

Neil D. Jones (345 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

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

Smn theorem (1,213 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

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

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

of the popular textbooks Theory of Computation: A Gentle Introduction and A Recursive Introduction to the Theory of Computation. He died of brain cancer

Sierpiński space (1,913 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

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

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

Chomsky normal form (1,926 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

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

P (complexity) (1,940 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. Rabin 1967. Cobham 1965

Rice–Shapiro theorem (3,454 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

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,626 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 (2,010 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,132 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

Lawrence Landweber (255 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. Member of the board

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

In computability theory, Selman's theorem is a theorem relating enumeration reducibility with enumerability relative to oracles. It is named after Alan

Spike response model (3,771 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

Charles E. Leiserson (821 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

Queue automaton (785 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

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

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

Best-first search (504 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

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

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

EXPSPACE (648 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

Silvio Micali (637 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

Linear bounded automaton (823 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

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

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

NP (complexity) (2,784 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

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

CYK algorithm (2,189 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

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

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 I. (1987)

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.

Chomsky hierarchy (1,348 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

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

Zohar Manna (403 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

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

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)

IP (complexity) (5,591 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

Leonard Adleman (832 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

L (complexity) (1,502 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

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

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

International Association for Cryptologic Research (1,411 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

Deterministic pushdown automaton (1,236 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 (298 words) [view diff] case mismatch 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

Complexity class (10,382 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

Jennifer Wortman Vaughan (637 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

Harry R. Lewis (4,524 words) [view diff] case mismatch in snippet view article find links to article

was an assembly language for PDP-11 computers. Elements of the Theory of Computation (1981, with Christos H. Papadimitriou)[LP81] covers automata theory

Grzegorczyk hierarchy (1,631 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)

*-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

AC (complexity) (575 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

State-transition table (781 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

Ryan Williams (computer scientist) (545 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

Christos Papadimitriou (981 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

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.

Hao Wang (academic) (941 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

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

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

Jack Copeland (1,264 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

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

Mathematics Subject Classification (1,395 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

NL (complexity) (1,570 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

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

Reduction (complexity) (1,658 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

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"

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

Stephen Smale (2,186 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

Mikhail Atallah (567 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

Faith Ellen (281 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

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

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

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

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

BlooP and FlooP (696 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

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

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

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

Cobham's thesis (685 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

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,793 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.

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

Andrew Yao (961 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

Ron Rivest (1,543 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

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

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

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

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

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

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

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

Infinite loop (2,605 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

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

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

Nick Pippenger (416 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

Function composition (3,772 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

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

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

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

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

Warren Sturgis McCulloch (2,759 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

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

Banach fixed-point theorem (2,745 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

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

Affordance (3,043 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

John McCarthy (computer scientist) (3,206 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

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

NP-completeness (3,617 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

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

Alan Cobham (mathematician) (333 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)

Event-driven finite-state machine (576 words) [view diff] case mismatch in snippet view article find links to article

McGraw-Hill, Inc. ISBN 0-07-049138-0. Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California:

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

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

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

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

Interactive proof system (2,746 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

Outline of physical science (5,641 words) [view diff] exact match in snippet view article find links to article

Computer science spans theoretical disciplines (such as algorithms, theory of computation, and information theory) to applied disciplines (including the design

Richard M. Friedberg (945 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. R

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

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

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

Eduardo D. Sontag (1,201 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

Lenore Blum (1,740 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

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

PCP theorem (1,770 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

Operational semantics (2,565 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

Denotational semantics (3,784 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

Circuit complexity (2,571 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

Error correction code (4,684 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

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)

Courant Institute of Mathematical Sciences (4,450 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

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'

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

Fermat pseudoprime (2,280 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.

Harvey Prize (431 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

NC (complexity) (3,078 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

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

Las Vegas algorithm (2,523 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

D. P. Sharma (1,507 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

Neurophilosophy (5,881 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

Madhan Karky (3,910 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)

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.

Boolean satisfiability problem (5,045 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 (730 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

Cook–Levin theorem (2,354 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

Konrad Zuse (4,562 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

Specified complexity (3,965 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

History of computer science (5,457 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

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

Oblivious transfer (2,019 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

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

ISBN 978-2-7056-6166-3. Martin, John (2003). Introduction to Languages and the Theory of Computation (3rd ed.). McGraw-Hill. ISBN 978-0-07-232200-2. Mazur, Joseph (2014)

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

Jelani Nelson (1,269 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

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)

Log-space reduction (1,358 words) [view diff] case mismatch 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

Kamala Krithivasan (225 words) [view diff] exact match in snippet view article find links to article

2024-10-29 Mahalingam, Kalpana; Rama, Raghavan (September 2018), "Theory of computation: P systems. Articles dedicated to Kamala Krithivasan on her 70th

Space hierarchy theorem (2,784 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

Code as data (728 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

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

Radiation therapy (14,009 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

Binary logarithm (5,128 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

Plankalkül (2,743 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

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

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

Anatol Slissenko (1,869 words) [view diff] exact match in snippet view article find links to article

Kiev, 1978 (In Russian). A. Slissenko. Complexity problems of theory of computation. Russian Mathematical Surveys, 36(6):23–125, 1981. Russian original

Jean Salençon (881 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

General semantics (6,599 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

Frame problem (4,820 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

True quantified Boolean formula (3,846 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

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

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

Issa Al-Ghaith (288 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

Probabilistic context-free grammar (5,242 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

Turing scheme (1,157 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

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

History of computing in the Soviet Union (6,475 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.

Algorithm characterizations (8,991 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 Markov, A. A. (1954)

Unconventional computing (4,694 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

List of University of California, Berkeley faculty (15,295 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

Event calculus (3,181 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 (780 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

Yao's principle (3,834 words) [view diff] case mismatch in snippet view article find links to article

in Atallah, Mikhail J.; Blanton, Marina (eds.), Algorithms and Theory of Computation Handbook: General Concepts and Techniques (2nd ed.), CRC Press,

Glossary of engineering: A–L (31,753 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,190 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

List of University of Texas at Dallas people (2,515 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

Rainbow Honor Walk (13,410 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

Legacy of Alan Turing (5,712 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 (124 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