Compute the set of nodes in G that satisfy EF

Assignment Help Python Programming
Reference no: EM132390036

CPTS515

Do in Python using pyEDA package .

0. Let G be a graph over 32 nodes (namely, node 0, , node 31). Forall 0 ≤ i,j ≤31, there is an edge from node i to node j iff (i + 3)%32 = j%32 or (i + 8)%32 = j%32. (% is the modular operator in C; e.g., 35% 32=3.) A node i is even if i is an even number. A node i is prime if i is a prime number. In particular, we define [even] as the set {0,2,4,6....30} and [prime] as the set { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} . We use R to denote the set of all edges in G.

1. (write-up) Let p be a CTL formula while [p] is the set of nodes in G that satisfy p.

Please design a fix-point iteration algorithm that computes [EF p](the set of nodes in G that satisfy EF p from R and [p]).

Please design a fix-point iteration algorithm that computes [EGp](the set of nodes in G that satisfy EGp from R and [p]).

You may first study the algorithms for [AGp] and [AF p].

2. (coding inPython)Every finite set can be coded as a BDD. Please write a Python program to compute [EG(even EFprime)] (the set of nodes that satisfy the formula EG( even EF prime).), and verify your answer by checking

node 5 satisfies EG(even Λ EF prime) and

node 6 doesnt satisfy EG(even Λ EF prime).

(Important: your code shall first encode R, [even], [prime] in BDDs using pyEDA and then using methods provided with the package, implement the iteration algorithms provided in 3 symbolically inBDD using methods in the package. Many students find methods BDD. compose()andBDD. smoothing() are quite useful in the package.)

3. (write-up) To make use of the idea of BDDs, a major difficulty is which graph is chosen to model a given set of data. When the graph is too large, the symbolic exploartion algorithm would not even run efficiently.  However, if the graph is too small, the modeling might not be even realistic. We now think about an example problem. Consider a finite set L of DNA strands, where each strand is simply a string on alphabet {A, T, C, G} (that is, a strand is a sequence of nucleotides, each of which is chosen from four nitrogen-containing nucleobases.).

One may use a deterministic finite automaton (DFA)1 M (which itself is a graph) to model the set L; i.e L ⊆ L(M ). That is, each strand w in L, there is a walk in M (from the initial state to an accepting state) such that the symbols sequentially collected on the transitions on the walk form exactly the w. Clearly, many many different M can be used to model L(e.g., M canbe ridiculously simplewithonly one state andaccepting every word onthe alphabet.).

Consequently,oneneed come up with ametric Q(M,L), which is a real number,to characterize the "precision" on using the given M to model L. When this is done, one can argue, for two given DFAs M1 and M2 which both model the given L, which model is more precise. Now, you need write a mini-paper (of 1 or 2 or more pages) in figuring out ways to define Q(M, L) and to design algorithms to compute Q(M, L).

Reference no: EM132390036

Questions Cloud

Describe a health-related issue you chose in girls or women : Briefly describe a health-related issue you chose in girls or women. Briefly describe how the program relates to at least two theories.
What are the characteristics of a concept : What is a concept? What are the characteristics of a concept? Discuss the process of critical thinking, and detail the two components of it as well.
Describe goals for the client based on presenting problem : In order to provide the appropriate intervention, social workers first need to have conducted a thorough assessment. Having a comprehensive understanding.
How can applied anthropology help make things safer : Discuss the reality that natural disasters have different effects and mortality rates in different economies. How can applied anthropology help make things.
Compute the set of nodes in G that satisfy EF : CPTS515- Design a fix-point iteration algorithm that computes the set of nodes in G that satisfy EF p from R and P. Design algorithms to compute Q
Determine the main idea of the article : Recall from Week 1 that main ideas and thesis sentences are really two sides of the same coin. Writers create thesis sentences. Readers pick out the main idea.
What you learned and found interesting about recent article : Please view the following article, and discuss what you learned and/or found interesting about this recent article on the latest findings.
Why were the parties unable to reach pareto optimality : Prior to the conflict stalling, how did the parties deal with the integrative and distributive aspects of the negotiation? Why were the parties unable to reach.
Describe the different divisions of the motor system : There are significant differences in the ability of individuals to perform complex motor skills. Discuss how the different divisions of the motor system.

Reviews

Write a Review

Python Programming Questions & Answers

  Write a python program to implement the diff command

Without using the system() function to call any bash commands, write a python program that will implement a simple version of the diff command.

  Write a program for checking a circle

Write a program for checking a circle program must either print "is a circle: YES" or "is a circle: NO", appropriately.

  Prepare a python program

Prepare a Python program which evaluates how many stuck numbers there are in a range of integers. The range will be input as two command-line arguments.

  Python atm program to enter account number

Write a simple Python ATM program. Ask user to enter their account number, and print their initail balance. (Just make one up). Ask them if they wish to make deposit or withdrawal.

  Python function to calculate two roots

Write a Python function main() to calculate two roots. You must input a,b and c from keyboard, and then print two roots. Suppose the discriminant D= b2-4ac is positive.

  Design program that asks user to enter amount in python

IN Python Design a program that asks the user to enter the amount that he or she has budget in a month. A loop should then prompt the user to enter his or her expenses for the month.

  Write python program which imports three dictionaries

Write a Python program called hours.py which imports three dictionaries, and uses the data in them to calculate how many hours each person has spent in the lab.

  Write python program to create factors of numbers

Write down a python program which takes two numbers and creates the factors of both numbers and displays the greatest common factor.

  Email spam filter

Analyze the emails and predict whether the mail is a spam or not a spam - Create a training file and copy the text of several mails and spams in to it And create a test set identical to the training set but with different examples.

  Improve the readability and structural design of the code

Improve the readability and structural design of the code by improving the function names, variables, and loops, as well as whitespace. Move functions close to related functions or blocks of code related to your organised code.

  Create a simple and responsive gui

Please use primarily PHP or Python to solve the exercise and create a simple and responsive GUI, using HTML, CSS and JavaScript.Do not use a database.

  The program is to print the time

The program is to print the time in seconds that the iterative version takes, the time in seconds that the recursive version takes, and the difference between the times.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd