The problem of finding the circular attributes in an grammar is considered. Two algorithms are proposed: the first is polynomial but yields conservative results while the second is exact but is potentially expontial. It is also shown that finding the circular attributes is harder than testing circularity.

Programs which manipulate pointers are hard to debug. Pointer analysis algorithms (originally aimed at optimizing compilers) may provide some remedy by identifying potential errors such as dereferencing NULL pointers by statically analyzing the behavior of programs on all their input data. Our goal is to identify the "core program analysis techniques" that can be used when developing realistic tools which detect memory errors at compile time without generating too many false alarms. Our preliminary experience indicates that the following techniques are necessary: (i) finding aliases between pointers, (ii) flow sensitive techniques that account for the program control flow constructs, (iii) partial interpretation of conditional statements, (iv) analysis of the relationships between pointers, and sometimes (v) analysis of the underlying data structures manipulated by the C program. We show that a combination of these techniques can yield better results than those achieved by state of the...

To improve the utilization of machine resources in superscalar processors, the instructions have to be carefully scheduled by the compiler.As internal parallelism and pipelining increases, it becomes evident that scheduling should be done beyond the basic block level.A scheme for global (intra-loop) scheduling is proposed, which uses the control and data dependence information summarized in a

Consideration is given to the design and implementation of a dialogue manager for large interactive dialogues. The dialogue manager described is aimed at fast dialogues which bother the user with a minimum number of questions. This is achieved by making efficient use of the screen area, both in correct and in erroneous situations, and by extracting information about yet-unanswered questions from already available answers.>

Circular attribute grammars appear in many data flow analysis problems. As one way of making the notion useful, an automatic translation of circular attribute grammars to equivalent non-circular attribute grammars is presented. It is shown that for circular attribute grammars that arise in many data flow analysis problems, the translation does not increase the asymptotic complexity of the semantic equations. Therefore, the translation may be used in conjunction with any evaluator generator to automate the development of efficient data flow analysis algorithms. As a result, the integration of such algorithms with other parts of a compiler becomes easier.

A machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units is considered. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm for producing an approximate solution is described and analyzed. For binary trees its worse-case cost is at most $\min (1.091,1 + {{(2\log n)} / n})$ times the optimal cost.

The problem of optimal scheduling of a job system for two dedicated processors is presented. A machine model with two functional units which can be either sequential or pipelined is considered. The complexity of optimal scheduling for a set of expressions on such machines is investigated. Some previous NP-completeness results are reviewed and several new ones are presented. For one restricted case, a polynomial-time algorithm is described and analyzed.>

We consider a machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm to produce an approximate solution is described and analyzed. For binary trees its worse case cost is at most 9.1% worse than the optimal cost.

We propose a new machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units. For this model, the evaluation of expression trees is considered. An efficient algorithm to produce an optimal order of evaluation is described and analyzed. For a tree with n vertices the algorithm runs in time Ο(n log2n). If the arithmetic operations have at most two arguments, the complexity goes down to Ο(n logn).

Consider a network of asynchronous processors communicating by sending messages over unreliable lines. There are many advantages to restrict all communications to a spanning tree. To overcome the possible failure of k

A methodology for transforming sequential recursive algorithms to distributive ones is suggested. The assumption is that the program segments between recursive calls have a distributive implementation. The methodology is applied to two k-selection algorithms and yields new distributed k-selection algorithms. Some complexity issues of the resulting algorithms are discussed.

The classical algorithm for testing unique decipherability of codes is improved by using McCreight's algorithm for constructing suffix trees. The complexity of the algorithm is O(nm) where n is the number of codewords and m is their total length. Efficiency is gained by avoiding repeatedly comparing subwords of the codewords.

An efficient algorithm for achieving distributed termination without introducing new communicaton channels and without delaying the basic computations ("freezing") is presented. The algorithm is related to the methodology of designing distributed programs where the programmer is relieved from the problem of distributed termination. An informal correctness proof and complexity analysis are included.

Given a ring (cycle) of n processes it is required to design the processes so that they will be able to choose a leader (a uniquely designated process) by sending messages along the ring. If the processes are indistiguishable there is no deterministic algorithm, and therefore probabilistic algorithms are proposed. These algorithms need not terminate, but their expected complexity (time or number of bits of communication) is bounded by a function of n. If the processes work asynchronously then on the average O(n log2n) bits are transmitted. In the above cases the size n of the ring was assumed to be known. If n is not known it is suggested first to determine the value of n and then use the above algorithm. However, n may only be determined probabilistically and any algorithm may yield an incorrect value. In addition, it is shown that the size of the ring cannot be calculated by any probabilistic algorithm in which the processes can sense termination.

A linear implementation of the optimal universal data compression methods of Lempel and Ziv is described.The main tool is McCreight's algorithm for constructing suffix trees.Both bounded and unbounded memory are considered.

We show that any biconnected graph with n nodes and m edges can be covered by simple circuits whose total length is at most $\min (3m,m + 6n)$. Our proof suggests an efficient algorithm for finding such a cover.

A layout for the shuffle-exchange network with O(N2/log3/2N) area is described. The layout combines ideas proposed by Thompson, Hoey, and Leiseron, and Preparata and Vuillemin. An interesting feature of the layout is that both the shuffle and the exchange edges have the same average length.

From the users' point of view, resource management schemes may be considered as an abstract data type. An abstract specification of such schemes using axioms holding in partial algebras and relatively distributed implementations (expressed as CSP programs) are given and analyzed. Then the idea of probabilistic implementation of guard scheduling is suggested, which allows completely distributed symmetric programs. It frees the designer of an algorithm from looking for specific probabilistic algorithms, by allowing the compiler to generate probabilistic target code from nonprobabilistic source code.

article Some Matching Problems for Bipartite Graphs Share on Authors: Steven L. Tanimoto Department of Computer Science, University of Washington, Seattle, WA and University of Connecticut, Storrs, Connecticut Department of Computer Science, University of Washington, Seattle, WA and University of Connecticut, Storrs, ConnecticutView Profile , Alon Itai Computer Science Department, Techmon-Israel Institute of Technology, Haifa, Israel Computer Science Department, Techmon-Israel Institute of Technology, Haifa, IsraelView Profile , Michael Rodeh IBM Israel Scientific Center, Haifa, Israel IBM Israel Scientific Center, Haifa, IsraelView Profile Authors Info & Claims Journal of the ACMVolume 25Issue 4Oct. 1978 pp 517–525https://doi.org/10.1145/322092.322093Online:01 October 1978Publication History 51citation1,847DownloadsMetricsTotal Citations51Total Downloads1,847Last 12 Months80Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. To find an almost minimum circuit an $O(n^2 )$ algorithm is presented. A direct algorithm for finding a minimum circuit has an $O(ne)$ behavior. It is refined to yield an $O(n^2 )$ average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are given. The first has an $O(e^{3/2})$ worst case bound ($O(n)$ for planar graphs); the second takes $O(n^{5/3})$ time on the average; the third has an $O(n^{\log 7} )$ worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with $O(n^2 \log n)$ average behavior.