ISSN:0010-3640    

DOI:10.1002/cpa.3160480902

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

ISSN:0010-3640    

DOI:10.1002/cpa.3160480903

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractA “recursively decomposable network” can be partitioned into a finite number of subnetworks that are smaller “versions of itself,” where the subnetworks are themselves recursively decomposable. Several interesting notions of such networks emerge depending on the collections of parameters chosen to model the relative behavioral characteristics that make a subnetwork a version of another. Examples of such parameters are permutation time, bandwidth, latency, topology, wires, degree, and size. This paper introduces and studies the class of networks that are recursively decomposable relative to bandwidth limitations, and the subclass of “recurrent networks” that are recursively decomposable relative to topology limitations.We show that anN‐node recursively decomposable into halves network with bandwidth‐inefficiency function β(x) must be at least\documentclass{article}\pagestyle{empty}\begin{document}$\frac{N}{2}\sum\nolimits_{i = l}^{\lg N}{\frac{1}{{\beta(2^i)}}}$\end{document}wires. This implies that the linear array, hypercube, and completely connected networks are all exactly optimal. The above lower bound is generalized to networks that are recursively decomposable, but not necessarily into halves. We show that the bound is tight up to a constant factor by exhibiting recurrent networks matching the above lower bounds.Our lower bound results both tighten and generalize a result of Meertens: no recurrent, fixed degree network can permute inO(logN) time. © 1996 John Wiley&Sons, Inc. ©1996 Jo

ISSN:0010-3640    

DOI:10.1002/cpa.3160480904

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractThis paper gives a brief history of the development of an approach to help students learn mathematical concepts at the post‐secondary level. The method uses ISETL, a programming language derived from SETL, to implement instruction whose design is based on an emerging theory of learning. Examples are given of uses of this pedagogical strategy in abstract algebra, calculus, and mathematical induction. © 1996 John Wiley&Sons, I

ISSN:0010-3640    

DOI:10.1002/cpa.3160480905

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractA program development methodology based on verified program transformations is described and illustrated through derivations of a high level bisimulation algorithm and an improved minimum‐state DFA algorithm. Certain doubts that were raised about the correctness of an initial paper‐and‐pencil derivation of the DFA minimization algorithm were laid to rest by machine‐checked formal proofs of the most difficult derivational steps. Although the protracted labor involved in designing and checking these proofs was almost overwhelming, the expense was somewhat offset by a successful reuse of major portions of these proofs. In particular, the DFA minimization algorithm is obtained by specializing and then extending the last step in the derivation of the high level bisimulation algorithm.Our experience suggests that a major focus of future research should be aimed towards improving the technology of machine checkable proofs — their construction, presentation, and reuse. This paper demonstrates the importance of such a technology to the verification of programs and program transformations. We believe that the utility of transformational systems to program development will ultimately rest on a practical program correctness technology. © 1996 John Wiley

ISSN:0010-3640    

DOI:10.1002/cpa.3160480906

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper we obtain a global attractivity result for the positive equilibrium of a nonlinear second‐order difference equation of the formxn+1= f(xn, xn+1),n= 0, 1, ⃛The result applies to the difference equationxn+1=A+bxn/A+n−1,n= 0, 1, ⃛Wherea, b, Aϵ (0, ∞). © 1996 John Wile

ISSN:0010-3640    

DOI:10.1002/cpa.3160480907

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractHereditarily finite sets and hypersets are characterized both as algorithmic data structures and by means of a first‐order axiomatization which, despite being rather weak, suffices to make the following two problems decidable:(1)Establishing whether a conjunctionrof formulae of the form: ∀ y1⃛∀ ym((y1ϵW1&⃛&ymϵWm) ←q), withqquantifier‐free and involving only the relators =, ϵ and propositional connectives, and eachyidistinct from allwj's, is satisfiable.(2)Establishing whether a formula of the form ∀y q, qquantifier‐free, is satisfiable.Concerning (1), an explicit decision algorithm is provided; moreover, significantly broad subproblems of (1) are singled out in which a classification — that we call the ‘syllogistic decomposition’ ofr— of all possible ways of satisfying the input conjunctionrcan be obtained automatically. For one of these subproblems, carrying out the decomposition results in a finite family of syntactic substitutions that generate the space of all solutions tor. In this sense, one has a unification algorithm.Concerning (2), a technique is provided for reducing it to a subproblem of (1) for which a decomposition method is available.The algorithmic complexity of the problems under study is highlighted; a generalization of the decidability results to a theory where sets are blended with free Herbrand functors is announced.

ISSN:0010-3640    

DOI:10.1002/cpa.3160480908

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractIn this paper, we examine several issues of bit‐parallel free space optical communication such as arbitration operations, fault tolerance, and connector alignment. © 1996 John Wiley&Sons, I

ISSN:0010-3640    

DOI:10.1002/cpa.3160480909

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractWe survey recent developments in algorithmic motion planning in robotics. © 1996 John Wiley&Sons, Inc

ISSN:0010-3640    

DOI:10.1002/cpa.3160480910

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

ISSN:0010-3640    

DOI:10.1002/cpa.3160480901

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY