Find link

Theory of computation not in CYK algorithm

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 200 found (453 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 (358 words) [view diff] exact match in snippet view article find links to article

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

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

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

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

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

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

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

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

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

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

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

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

McCarthy 91 function (1,115 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

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

Lawrence Landweber (263 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

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

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

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

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

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

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

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

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

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

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

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

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.

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)

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

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

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

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)

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)

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

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

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

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

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

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

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

Linear search (1,271 words) [view diff] case mismatch in snippet view article find links to article

(1999). "Chapter 2: Searching". In Atallah (ed.). Algorithms and Theory of Computation Handbook. CRC Press. pp. 2–3. ISBN 0849326494. Horvath, Adam. "Binary

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

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

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

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

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

Syntax (programming languages) (1,902 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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

"Dynamic graph algorithms". In CRC Handbook of Algorithms and Theory of Computation, Chapter 22. CRC Press, 1997. Eppstein, David; Italiano, Giuseppe;

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.

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

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

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

Computation tree (298 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),

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,

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

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

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

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

Gödel Prize (2,200 words) [view diff] exact match in snippet view article find links to article

extractor with polylogarithmic min-entropy, resolving a central problem in the theory of computation that had been open for almost three decades." 2016

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

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

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

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

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

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

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

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

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

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)

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

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:

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

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

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

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

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

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

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

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

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

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

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

Outline of physical science (5,643 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

Open addressing (1,225 words) [view diff] case mismatch in snippet view article find links to article

Poblete, Patricio V. (1999). "Chapter 2: Searching". In Atallah (ed.). Algorithms and Theory of Computation Handbook. CRC Press. pp. 2–7. ISBN 0849326494.

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

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

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

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

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

(1): 37–61. doi:10.1145/3586165.3586172. Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. London: Springer-Verlag. pp. 119–127

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'

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

Turochamp (2,106 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)

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'

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.

Hash table (6,078 words) [view diff] case mismatch in snippet view article find links to article

(1999). "Chapter 2: Searching". In Atallah (ed.). Algorithms and Theory of Computation Handbook. CRC Press. pp. 2–6. ISBN 0849326494. Lech Banachowski

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

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

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

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

NC (complexity) (3,087 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,932 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 (568 words) [view diff] case mismatch in snippet view article find links to article

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

Boolean satisfiability problem (4,824 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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

Addition (10,217 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)

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

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

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

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

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

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

Two-dimensional pattern matching (529 words) [view diff] case mismatch in snippet view article find links to article

13: General Pattern Matching". In Atallah (ed.). Algorithms and Theory of Computation Handbook. CRC Press. pp. 13–11. ISBN 0849326494. Bird, Richard S

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.

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

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

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

Logic programming (10,752 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

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

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

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

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

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.

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

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)

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

Perceptrons (book) (5,184 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

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

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,413 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,815 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