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 the concepts of confidentiality integrity and

Describe the concepts of confidentiality, integrity, and availability (C-I-A), and explain each of the seven domains of a typical IT infrastructure. Summarize the threat triad, and explain how security personnel can main ...

Compare and contrast traditional outsourcing with the

Compare and contrast traditional outsourcing with the Software as a Service. Under what conditions do you think a company should choose SaaS over traditional outsourcing? Explain your views and discuss them with your pee ...

Consider the following problem descriptionemployees receive

Consider the following problem description: Employees receive their biweekly paychecks. They are paid their hourly rates for each hour worked; however, if they worked more than 40 hours per week, they are paid at 150 per ...

Suppose a vending machine contains products and users

Suppose a vending machine contains products, and users insert coins into the vending machine to purchase products. Draw a UML diagram showing the dependencies between the classes VendingMachine, Coin, and Product.

Implement a votingmachine class that can be used for a

Implement a VotingMachine class that can be used for a simple election. Have methods to clear the machine state, to vote for a Democrat, to vote for a Republican, and to get the tallies for both parties. Extra credit if ...

The text derives the following formula for the difference

The text derives the following formula for the difference of a product: How can this formula be correct, when the left-hand side is symmetric with respect to u and v but the right-hand side is not?

Assume that you have been asked to review the power needs

Assume that you have been asked to review the power needs for a standalone computer system which processes important but noncritical data and does not have to be online at all times, and which stores valuable data that c ...

Write a function that converts a phrase into pig latin a

Write a function that converts a phrase into pig Latin. A word is converted to pig Latin by removing the first character of the word, placing it at the back of the word, and adding the characters "ay" to the word. For ex ...

For hash functions it is crucial to have a sufficiently

For hash functions it is crucial to have a sufficiently large number of output bits, with, e.g., 160 bits, in order to thwart attacks based on the birthday paradox. Why are much shorter output lengths of, e.g., 80 bits, ...

In the segregation model the agents look to their

In the Segregation model, the agents look to their neighborhood composition to decide if they are happy. Can you make the size of shape of the neighborhood a parameter? How does this change the results of the model?

  • 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

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

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