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

1 how would you fi x the false sharing issue that can

1. How would you fi x the false sharing issue that can occur? 2. Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that ...

1 calculate the cpi for the processor in the table using 1

1. Calculate the CPI for the processor in the table using: 1) only a first level cache, 2) a second level direct-mapped cache, and 3) a second level eight-way set associative cache. How do these numbers change if main me ...

A variation on the basic binary algorithm involves not

A variation on the basic binary algorithm involves not centering the algorithm around the lower and upper limits. Instead, two alternate parameters are maintained, one that points to the middle of the array segment still ...

1 if the processor has forwarding but we forgot to

1. If the processor has forwarding, but we forgot to implement the hazard detection unit, what happens when this code executes? 2. If there is forwarding, for the first five cycles during the execution of this code, spec ...

Your manager has tasked you with creating a remote employee

Your manager has tasked you with creating a Remote Employee Connection guide for IT. This guide will assist IT in setting up remote (work-from-home) employees to access the company's Intranet. These employees will use a ...

When does an ospf router send each of the following

When does an OSPF router send each of the following messages? a. hello b. data description c. link-state request d. link-state update e. link-state acknowledgment

1 compare and contrast the ideas of virtual memory and

1. Compare and contrast the ideas of virtual memory and virtual machines. How do the goals of each compare? What are the pros and cons of each? List a few cases where virtual memory is desired, and a few cases where virt ...

In some applications particular information needs to be

In some applications, particular information needs to be retrieved from a list with a much higher frequency than other information. Under these conditions the best way to arrange the list is to put the most frequently re ...

1 what is the size of the key space if all 8 characters are

1. What is the size of the key space if all 8 characters are randomly chosen 8-bit ASCII characters? How long does an average key search take with a single PC? 2. How many key bits are used, if the 8 characters are rando ...

How could an evolutionary process like ge be used to

How could an evolutionary process, like GE be used to evolve 1. Neural networks? 2. Production systems? Describe in some detail. In particular, how would the crossover operation be implemented? Comment on whether or not ...

  • 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