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

Discuss the impact of threaded binary tree on the tree

Discuss the impact of threaded binary tree on the tree traversal procedure. g. Obtain the optimal Huffman codes for the messages (M1,...,M7) with relative frequencies (q1,...,q7)=(4,5,7,8,10,12,20). Draw the decode tree ...

1 in what fraction of all cycles is the data memory used2

1. In what fraction of all cycles is the data memory used? 2. In what fraction of all cycles is the input of the sign-extend circuit needed? What is this circuit doing in cycles in which its input is not needed? 3. When ...

Directory services4 page word doc and 1 visioyou were hired

Directory Services 4 page word doc and 1 Visio You were hired as a consultant to analyze an existing Windows Server environment in a utilizing Windows Server 2003 and 2008. The local IT administrator has heard about virt ...

Search the world wide web for job descriptions of project

Search the World Wide Web for job descriptions of project managers. You can use any number of Web sites, including www.monster.com or www.dice.com, to find at least ten IT-related job descriptions. What common elements d ...

1 do research in the literature on sensorless vector

1. Do research in the literature on sensorless vector control-based systems and write a summary report. 2. Do research in the literature on space vector modulation as applied to vector control-based systems and write a s ...

Assignment1 synchronization is a major concern when

Assignment 1 Synchronization is a major concern when designing __________communication paths. 2. Research Question: How many STORE instructions are used in the lc3 Instruction set architecture.. 3. Superscalar architectu ...

Identify ten validation tests and techniques used to

Identify ten validation tests and techniques used to enhance the validity of data input; be sure to give an example of each in your discussion. How are these tests handled? This assignment must be a neat, professional pr ...

1 you can read the value instance variable of the counter

1. You can read the value instance variable of the Counter class with the getValue accessor method. Should there be a setValue mutator method to change it? Explain why or why not. 2. a. Show that the BankAccount(double i ...

Write a gui application for the webbuy company that allows

Write a GUI application for the WebBuy Company that allows a user to compose the three parts of a complete email message: the "To:", "Subject:" and "Message:" text. The "To:", and "Subject:" Text areas should provide a s ...

Credit card number check the last digit of a credit card

Credit Card Number Check. The last digit of a credit card number is the check digit, which protects against transcription errors such as an error in a single digit or switching two digits. The following method is used to ...

  • 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