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

Describe a phenomenon that you think it would be

Describe a phenomenon that you think it would be interesting to model using ABM. What are the agents in this model? What properties do they have? What kind of actions can the agents take? What kind of environment do the ...

A manchester signal has a data rate of 100 kbps using

A Manchester signal has a data rate of 100 Kbps. Using Figure 4.8, calculate the value of the normalized energy (P) for frequencies at 0 Hz, 50 KHz, 100 KHz.

The demand for sub assembly s is 110 in week 7 each unit of

The demand for sub assembly S is 110 in week 7. Each unit of S requires 2 units of T and 1 unit of U.Each unit of T requires 1 unit of V, 1 Unit of W and 2 units of X. Finally, each unit of U requires 2 units of Y and 3 ...

Write a program that produces random permutations of the

Write a program that produces random permutations of the numbers 1 to 10. To generate a random permutation, you need to fill an array with the numbers 1 to 10 so that no two entries of the array have the same contents. Y ...

A circle 2n - 1 units in diameter has been drawn

A circle, 2n - 1 units in diameter, has been drawn symmetrically on a 2n × 2n chessboard, illustrated here for n = 3: a How many cells of the board contain a segment of the circle? b Find a function f(n, k) such that exa ...

Q1 describe the three models of cloud computing based on

Q1: Describe the three models of cloud computing based on the NIST cloud computing reference architecture. List the advantages and disadvantages of each model. Q2: What are the major network management functions? Q3: Des ...

With the number of people now capable of accessing the

With the number of people now capable of accessing the Internet from mobile devices, it is crucial that organisations develop mobile versions of their Web sites. Whether you have experience developing mobile Web sites or ...

Instructionsanswer all questions please show your working

Instructions Answer all questions. Please show your working for calculations. Formatting your assignment: - Please submit your assignment online as one document in PDF format. This format locks the information and is par ...

Write a function that counts the occurrences of a word in a

Write a function that counts the occurrences of a word in a string. The function should return an integer. Do not assume that just one space separates words and a string can contain punctuation. Write the function so tha ...

1 in a graph if we know that the shortest path from node a

1. In a graph, if we know that the shortest path from node A to node G is (A → B → E → G), what is the shortest path from node G to node A? 2. Assume the shortest path in a graph from node A to node H is A → B → H. Also ...

  • 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

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen