Class Note for CMPSCI 601 at UMass(47)
Class Note for CMPSCI 601 at UMass(47)
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for CMPSCI 601 at UMass(47)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Uses of Greek Letters and Other Symbols in CMPSCI 601 letter name typical uses in CMPSCI 601 a alpha formula etc 6 beta formula V gamma formula P Gamma alphabet vocabulary set of formulas 6 delta formula transition function A Delta change new old 6 epsilon empty string small positive real number C zeta constant zero function 77 eta mapping 6 theta formula 9 Theta L iota H kappa cardinal number program counter A lambda function abstraction e g Axwz M mu interpretation function on terms minimization function V nu Xi 0 omicron 7139 pi 314159265 prime number H Pi set of predicate symbols proof product p rho 039 sigma successor function symbol in E 2 Sigma alphabet vocabulary set of formulas sum 739 tau T Upsilon p phi formula ltlgt Phi set of formulas SO formula set of function symbols X chi characteristic function 7 psi formula Kl Psi set of formulas secondorder formula to omega formula 9 Omega lower bound symbol name typical meaning or uses in CMPSCI 601 number sign separator aw number of a s in w star 2 set of all nite words from E 3 less than or equal less than or equal is reducible to substructure of intersection intersection U union union L bottom false in a logical formula D box end of proof de nition etc cdot indicates place for an argument multiplication o circ composition or concatenation Contradiction contradiction in informal metamathematical statement 2 iso isomorphic L downarrow M w means M converges on input w Q emptyset emptyset E equiv equivalent semantically equivalent elementarily equivalent gt is an abbreviation for eg a a B gt a V B 3 exists there exists V forall for all ceiling smallest integer greater than or equal to oor largest integer less than or equal to iff iff if and only if land logical and V lor logical or lnot logical not a righta1row implies in a logical formula f A a B righta1row f is a function from A to B gt gt mapsto a gt gt b means that the map takes a to b i Rightarrow implies in informal metamathematical statement lt gt leftrightarrow iff in a logical formula gt Leftrightarrow iff in informal metamathematical statement log log log base 2 models A l p means p is true in A F proves P F p means p can be proved from P L downarrow M w means M converges on input w nealrow M w means M diverges on input w 69 oplus exclusive or sum mod 2 sim has same cardinality is equivalent to p power set MS A l A Q S U sqcup space symbol on TM tape Q subseteq subset or equal to C psubset proper subset of T top true in a logical formula D triangleright left marker on TM tape other letters name typical meaning or uses in CMPSCI 601 cal A logical structure cal B logical structure cal C complexity class cal L language M language accepted by M be the set of natural numbers N 071727 be the set of rational numbers be the set of real numbers Nwozumm s bfZ 12 77 the set ofintegers Z 7 727170 Z o aleph 0 cardinality of N name Complexity Measures DSPACE deterministic space NSPACE nondeterministic space DTIME deterministic time NTIME nondeterministic time ASPACE alternating space ATIME alternating time name Complexity Classes 126 recursively enumumerable sets 00126 sets whose complements are re Recursive recursive sets Primitive Recursive primitive recursive sets EXPTIME exponential time DTIME2 1 PSPACE polynomial space DSPACE 7101 PH polynomialtime hierarchy NP nondeterministic polynomial time NTIMEnO1 P polynomial time DTIME 7101 NL nondeterministic logspace NSPACElog n L logspace DSPACElog n CFL contextfree languages Regular regular languages
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'