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

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

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

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 (351 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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"

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

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

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

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

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

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

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

Hans-Joachim Bremermann (506 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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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:

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

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

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

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

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

Time complexity (4,997 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,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

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

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

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

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

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

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

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

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)

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

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'

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

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.

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

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

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

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

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

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

Madhan Karky (3,931 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.

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

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

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

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

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

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

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

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

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

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

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)

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

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

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)

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

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

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

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

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

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.

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

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

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

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

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

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

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.

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,

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

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

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