Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

A program with two integer variables is universal. Now, we consider a special form of four variable programs. Let G = (V; E) be a directed graph, where V is a finite set of the nodes, and E ⊆V X V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final node. Let x1; x2; x3; x4 be four non-negative integer variables. Additional, we decorate each edge with one of the subsequent instructions: (1 ≤i≤ 4)

xi:= xi + 1;
xi:= 0;
xi == c? (c is a non-negative integer)

The result is called a decorated graph (we still use G to denote it). The semantics of a decorated graph is straight forward. It carries out from the initial node with x1; x2; x3; x4 being 0, then walks along with the graph. G can walk an edge (v, v') if all of the following conditions are satisfied: for each 1 ≤i≤4,

• If the edge is decorated with instruction xi: = xi + 1 for some i, the new value of xi is one more than the old value, and all the other xj(j ≠i) is unchanged.
• If the edge is decorated with instruction xi:= 0, the new value of xi is set to 0, and all the other xj (j ≠i) is unchanged.
• If the edge is decorated with instruction xi == c?, the value of xi should be c.

If at a node, G has more than one edge that can be walked, then G non-deterministically selects one. If at a node G has no edge that can be walked, then G crashes (i.e., do not walk any further). We say that a decorated graph G is terminating if G can walk from an initial node to a final node and at final node the values of x1; x2; x3; x4 satisfy the following constraint:

x1 = x2 = x3 = x4:

Demonstrate me an algorithm that answers (yes/no) whether G is terminating or not. (To correct a common misunderstanding, I shall point out that a walk could be arbitrarily long even although there are only 10 nodes in the graph! So, don't even try depth/breadth first search.)

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91278

Have any Question? 


Related Questions in Computer Engineering

Assume that a program will experience 200 failures in

Assume that a program will experience 200 failures in infinite (6) time. It has now experienced 100. The initial failure intensity was 20 failures/CPU hr. (i) Determine the current failure intensity (ii) Find the decreme ...

How technology affects social skill developmentsome people

How Technology affects Social Skill Development Some people feel that technology has made our world smaller and more social with the ability to communicate 24/7 via email, use social networking, and text, IM. Others say ...

Explain why from an economic point of view towing a car

Explain why from an economic point of view towing a car illegally parked rather than just ticketing it provides a better incentive (for both rich and low income individuals) not to break the law.

Write the code to call a function whose name is sendnumber

Write the code to call a function whose name is send_number. There is one argument for this function, which is an int. Send 5 as an argument to the function.

Suppose that the terminals of an electrical device are

Suppose that the terminals of an electrical device are labeled a and b. If vab=-15V, how much energy is exchanged when a positive charge of 4C moves through the device from a to b? Is the energy delivered to the device o ...

Assume you are hired to manage a very large it project such

Assume you are hired to manage a VERY large IT project such as the initial creation of Amazon.com. Write a paragraph describing the project and then provide a list of the stakeholders for the project and describe their r ...

This post needs to be 400 words1 using your book and the

This post needs to be 400 words 1) Using your book and the Internet, please explain the following Password-Cracking Methods: a. Brute Force Attack b. Dictionary Attack c. Syllable Attack d. Rule-Based Attack e. Hybrid At ...

Research project building a theory of data mining requires

(Research project) Building a theory of data mining requires setting up a theoretical framework so that the major data mining functions can be explained under this framework. Take one theory as an example (e.g., data com ...

A explain the trade-off that exists in concurrency controlb

a. Explain the trade-off that exists in concurrency control. b. Define an atomic transaction and explain why atomicity is important.

In example 1 why is the data type for the postal code field

In Example 1, why is the data type for the Postal Code field CHAR and not SMALLINT or INTEGER? Is the length of the field long enough? Why or why not? EXAMPLE 1 Use SQL to create the Rep table by describing its layout.

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate