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

Why are guards considered the most effective form of

Why are guards considered the most effective form of control for situations that require decisive action in the face of unfamiliar stimuli? Why are they usually the most expensive controls to deploy? When should dogs be ...

1 what is the difference between a compiler and an

1. What is the difference between a compiler and an interpreter? 2. What are the advantages of (a) a compiler over an interpreter (b) an interpreter over a compiler? 3. What advantages are there to a language-processing ...

Suppose that 95 of the execution time in a certain program

Suppose that 95% of the execution time in a certain program is due to code that can be split into N independent parts each of which can be executed by a separate processor. The remaining 5% is sequential and must execute ...

Design and implement a left and right justification

Design and implement a left and right justification algorithm that inserts extra spaces after the longest word first, then after the second longest word and so on. In your implementation by making certain assumptions, tr ...

Writenbspa 4- to 6-page paper use diagrams and tables

Write  a 4- to 6-page paper (use diagrams and tables whenever possible) to: Describe Open Systems Interconnection (OSI) protocol model and how data flows through the model. Identify major TCP/IP protocols within the fram ...

Assignment -you can generally assume that code shown in the

Assignment - You can generally assume that code shown in the questions is intended to be syntactically correct, unless something in the question or one of the answers suggests otherwise. Q1. Given the following statement ...

Programming assignmentbackground informationfor this

Programming Assignment Background information For this assignment you need to write an object-oriented console application in the Java programming language which adheres to basic object-oriented programming principles sh ...

1 fill in the blanks the 835 mhz bandwidth in bluetooth is

1. Fill in the blanks. The 83.5 MHz bandwidth in Bluetooth is divided into_____ channels, each of ______ MHz. 2. What is the spread spectrum technique used by Bluetooth? 3. What is the modulation technique in the radio l ...

1 a network consists of n hosts assuming that cryptographic

1. A network consists of n hosts. Assuming that cryptographic keys are distributed on a per-hostpair basis, compute how many different keys are required. 2. One cryptographic checksum is computed by applying the DES in C ...

1 comment on the reasons for the rapid growth of the

1. Comment on the reasons for the rapid growth of the Android operating system. 2. Recently Apple's iOS4 encryption was hacked by a Russian; compare and discuss the weaknesses in the iOS4 disclosed by the Russian company ...

  • 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