Sometime = always + recursion ≡ always on the equivalence of the intermittent and invariant assertions methods for proving inevitability properties of programs

Summary We propose and compare two induction principles called always and sometime for proving inevitability properties of programs. They are respective formalizations and generalizations of Floyd invariant assertions and Burstall intermittent assertions methods for proving total correctness of sequential programs whose methodological advantages or disadvantages have been discussed in a number of previous papers. Both principles are formalized in the abstract setting of arbitrary nondeterministic transition systems and illustrated by appropriate examples. The sometime method is interpreted as a recursive application of the always method. Hence always can be considered as a special case of sometime. These proof methods are strongly equivalent in the sense that a proof by one induction principle can be rewritten into a proof by the other one. The first two theorems of the paper show that an invariant for the always method can be translated into an invariant for the sometime method even if every recursive application of the later is required to be of finite length. The third and main theorem of the paper shows how to translate an invariant for the sometime method into an invariant for the always method. It is emphasized that this translation technique follows the idea of transforming recursive programs into iterative ones. Of course, a general translation technique does not imply that the original sometime invariant and the resulting always invariant are equally understandable. This is illustrated by an example.     

Monte Carlo modelling of electron beam lithography: a scaling law

The theorem of Dimensional Analysis, usually applied to the inference of physical laws, is for the first time applied to the derivation of interpolation curves of numerical data, leading to a simplified dependence on a reduced number of arguments , dimensionless combination of variables. In particular, Monte Carlo modelling of electron beam lithography is considered and the backscattering coefficient addressed, in case of a general substrate layer, in the elastic regime and in the energy range 5 to 100 keV. The many variables involved (electron energy, substrate physical constants and thickness) are demonstrated to ultimately enter in determining through asingle dimensionless parameter ₀. Thus, a scaling law is determined, an important guide in microsystem designing, indicating, if any part of the configuration is modified, how the other parameters should change (or scale) without affecting the result. Finally, a simple law =83 ₀ is shown to account for all variations of the parameters over all substrates of the periodic table.     

Continuous reductions among combinatorial optimization problems

Summary Many reductions among combinatorial problems are known in the context of NP-completeness. These reductions preserve the optimality of solutions. However, they may change the relative error of approximative solutions dramatically. In this paper, we apply a new type of reductions, called continuous reductions. When one problem is continuously reduced to another, any approximation algorithm for the latter problem can be transformed into an approximation algorithm for the former. Moreover, the performance ratio is preserved up to a constant factor. We relate the problem Minimum Number of Inverters in CMOS-Circuits, which arises in the context of logic synthesis, to several classical combinatorial problems such as Maximum Independent Set and Deletion of a Minimum Number of Vertices (Edges) in Order to Obtain a Bipartite (Partial) Subgraph.     

Massively parallel SIMD simulation of markovian DEDS: Event and time synchronous methods

We examine two schemes for parametric parallel simulation on SIMD supercomputers. In SIMD machines, the parallel processors execute a common instruction stream using local data-under the control of a front-end processor. In contrast to most parallel simulation approaches-which simulate a single system using multiple processors-we simulate distinct parametric variants at each processor. We extract some of the common computation embedded in these simulations and perform it on the front-end, leaving the rest to the parallel processors.The first simulation approach, which we call time synchronous, is essentially Vakili's standard clock. This approach generates a uniformized event process on the front-end processor which is thinned at each back-end processor based on local state information. The second scheme, which we call event synchronous, generates a standard Poisson process on the front-end, which is time-scaled and marked on the back-end processors.We develop a framawork for comparing these methods based on their simulated event rate (number of simulated events per real time unit). We show that the time synchronous method can be tuned to optimize the event rate for a given family of systems and we solve this optimal standard clock problem for several test cases. Finally we describe implementation issues peculiar to the SIMD architecture. Our focus is primarily on the M/M/1/K queue, but the methods extend to more general Jackson networks.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

A Stylometric Analysis of Ya?ar Kemal’s ? nce Memed Tetralogy

We analyze four nce Memed novels of Yaar Kemal using six style markers: most frequent words, syllable counts, word type – or part of speech – information, sentence length in terms of words, word length in text, and word length in vocabulary. For analysis we divide each novel into five thousand word text blocks and count the frequencies of each style marker in these blocks. The style markers showing the best separation are most frequent words and sentence lengths. We use stepwise discriminant analysis to determine the best discriminators of each style marker. We then use these markers in cross validation based discriminant analysis. Further investigation based on multiple analysis of variance (MANOVA) reveals how the attributes of each style marker group distinguish among the volumes.     

Spectrographic analysis and patterns in pronunciation

Though there are good reasons to improve instruction in pronunciation, the teaching of pronunciation has lost popularity among language teachers. This is because the traditional indirect analyses of sounds according to places and manners of articulation are clumsy when applied to classroom teaching. By shifting the focus of instruction to the direct feedback of real-time acoustic analysis in the visual mode, instructors are free from the complex and often unproductive terminology of articulatory phonetics, and students are free from the burden of translating instructors' general comments such as try again or repeat after me into plans for specific changes. Garry Molholt is Assistant Professor of Linguistics and English as a Second Language, and Coordinator of Computer Assisted Instruction. His research interests are the applications of speech processing to instruction in the acquisition of second language phonology. He has published Computer Assisted Instruction in Pronunciation for Chinese Speakers of American English, in TESOL Quarterly, and (with Ari Presler), Correlation between Human and Machine Ratings of Test of Spoken English Reading Passages, in Technology and Language Testing.     

Meaningful Alignments

We propose a method for detecting geometric structures in an image, without any a priori information. Roughly speaking, we say that an observed geometric event is meaningful if the expectation of its occurences would be very small in a random image. We discuss the apories of this definition, solve several of them by introducing maximal meaningful events and analyzing their structure. This methodology is applied to the detection of alignments in images.     

Automated Deduction Techniques for the Management of Personalized Documents

This work is about a real-world application of automated deduction. The application is the management of documents (such as mathematical textbooks) as they occur in a readily available tool. In this Slicing Information Technology tool, documents are decomposed (sliced) into small units. A particular application task is to assemble a new document from such units in a selective way, based on the user's current interest and knowledge. It is argued that this task can be naturally expressed through logic, and that automated deduction technology can be exploited for solving it. More precisely, we rely on first-order clausal logic with some default negation principle, and we propose a model computation theorem prover as a suitable deduction mechanism. Beyond solving the task at hand as such, with this work we contribute to the quest for arguments in favor of automated deduction techniques in the real world. Also, we argue why we think that automated deduction techniques are the best choice here.