### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(47)

### View Full Document

## 12

## 0

## 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.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(47)

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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.