Images of AFL under certain families of homomorphisms

An AFL is a family of sets of words closed under six basic operations. It is shown that a certain family of homomorphic images of sets in an AFL is an AFL. Then two families of sets related to tape-bounded nondeterministic Turing acceptors are shown to coincide and be an AFL.Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under contract F1962867C0008, the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67A, and by the National Science Foundation, Grant No. GJ454.Part of this work was also done at the System Development Corporation, Santa Monica, Calif.     

Control sets on grammars

Given a setC of strings of rewriting rules of a phrase structure grammarG, we consider the setL _c (G) of those words generated by leftmost derivations inG whose corresponding string of rewriting rules is an element ofC. The paper concerns the nature of the setL _c (G) whenC andG are assumed to have special form. For example, forG an arbitrary phrase structure grammar,L _c (G) is an abstract family of languages ifC is an abstract family of languages, andL _c (G) is bounded ifC is bounded.Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F1962867C0008, and by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67.     

Quasi-realtime languages

The quasi-realtime languages are seen to be the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a nondeterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.The research reported in this paper was announced at the ACM Symposium on the Theory of Computing, Marina del Rey, California, May, 1969. This research has been supported in part by Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-68-C-0029.     

Multi-stack-counter languages

A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasirealtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive-moves. For each positive integerk let be the family of languages accepted byk-stack-counter acceptors (k-counter acceptors). Each is a principal AFL closed under reversal but not under-free substitution or under intersection. Also, and a specific language in each, is exhibited. For each and there are noi andj such that. It is shown that a quasi-real-timek-stackcounter acceptor is equivalent to one operating in non-deterministic real time. Lastly, it is shown that acceptance by final state of ak-stack-counter acceptor is equivalent to acceptance by empty tape and final state.Also formerly with System Development Corporation, Santa Monica, California. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-70-C-0023; by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR No. F44620-70-C-0013; and by NSF Grant No. GJ454.     

Homomorphisms between stochastic sequential machines and related problems

The problem of finding a stochastic sequential machine with minimal number of states and homomorphic to a given machine is studied in various aspects. The methods used for investigating the above problem are based upon the properties of a certain convex polyhedron associated with the given machine.The research reported herein was supported by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force under AFOSR Grant AFAFOSR-639-67.On leave from Technion, Israel Institute of Technology, Haifa, Israel.     

Chains of full AFL's

If a full AFL is not closed under substitution, then ô , the result of substituting members of into, is not substitution closed and hence generates an infinite hierarchy of full AFL's. If ₁ and ₂ are two incomparable full AFL's, then the least full AFL containing ₁ and ₂ is not substitution closed. In particular, the substitution closure of any full AFL properly contained in the context-free languages is itself properly contained in the context-free languages. If any set of languages generates the context-free languages, one of its members must do so. The substitution closure of the one-way stack languages is properly contained in the nested stack languages. For eachn, there is a class of full context-free AFL's whose partial ordering under inclusion is isomorphic to the natural partial ordering onn-tuples of positive integers.This paper was completed while the author was in the Division of Engineering and Applied Physics of Harvard University. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under contracts F-1962870C0023 and F-1962868C0029, and by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67A and the Division of Engineering and Applied Physics of Harvard University.     

A partition on a Bernoulli shift which is not weakly Bernoulli

In an attempt to further classifyK-automorphism D. Ornstein suggested (orally) a stronger mixing property calledweak Bernoulli (together with N. Friedman he proved that if a generator has this property then the transformation is isomorphic to a Bernoulli shift). I show that in a Bernoulli shift there is a partition which is not weak Bernoulli. I use the following theorem: The shift on a regular stationary Gaussian process is isomorphic to a Bernoulli shift.Research sponsored by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force, under Grant AF-AROSR-1312-67. Present address: Mathematics Institute, University of Warwick, Coventry CV4 7AL, England.     

On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation

This paper characterizes the class of closed and (M, N)-recognizable languages in terms of certain structural aspects of relevant automata. This characterization leads to algorithms that effectively compute the supremal (M, N)-recognizable sublanguage of a given language. One of these algorithms is used, in an alternating manner with an algorithm which yields the supremal (∑_u, N)-invariant resulting algorithm is proved. An example illustrates the use of these algorithms. This research was supported in part by the Air Force Office of Scientific Research under Grant No. AFOSR-86-0029, in part by the National Science Foundation under Grant No. ECS-8412100, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract No. F49620-86-C-0045     

The calculation of Sobolev's ϕ function of radiative transfer via numerical inversion of Laplace transforms

The linear integral equation of convolution type of Sobolev's function ϕ is solved computationally using a new method for the numerical inversion of Laplace transforms. This research is sponsored by the United States Air Force under Project RAND —Contract No. AF 49 (638), 1700—monitored by the Directorate of Operational Requirements and Development Plans, Deputy Chief of Staff, Research and Development Hq, USAF. Views or conclusions contained in this paper should not be interpreted as representing the official opinion or policy of the United States Air Force.     

Analysis of an identification algorithm arising in the adaptive estimation of Markov chains

We investigate an algorithm applied to the adaptive estimation of partially observed finite-state Markov chains. The algorithm utilizes the recursive equation characterizing the conditional distribution of the state of the Markov chain, given the past observations. We show that the process “driving” the algorithm has a unique invariant measure for each fixed value of the parameter, and following the ordinary differential equation method for stochastic approximations, establish almost sure convergence of the parameter estimates to the solutions of an associated differential equation. The performance of the adaptive estimation scheme is analyzed by examining the induced controlled Markov process with respect to a long-run average cost criterion. This research was supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860 and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

The algebraic specification of abstract data types

Summary There have been many recent proposals for embedding abstract data types in programming languages. In order to reason about programs using abstract data types, it is desirable to specify their properties at an abstract level, independent of any particular implementation. This paper presents an algebraic technique for such specifications, develops some of the formal properties of the technique, and shows that these provide useful guidelines for the construction of adequate specifications.Supported in part by the National Science Foundation under grant MCS-76-06089 and the Joint Services Electronics Program monitored by the Air Force Office of the Scientific Research under contract F44620-72C-0061Supported in part by the National Research Council of Canada.     

An implementation base for efficient data structuring

The specification of data structure in higher-level languages is isolated from the related specifications of data allocation and binding of names. Structure specification is claimed to be the definition of the accessing (addressing) function for items having the structure. Conventional techniques for data structure isolation in higher-level languages are examined and are found to suffer from a lack of clarity and efficiency. The means by which data structure accessors may be defined in Bliss, the specification of their association with named, allocated storage, and their automatic invocation by reference to the named storage only, are discussed. An example is presented which illustrates their efficient implementation and their utility for separating the activities, of data structure programming and algorithmic programming.This work was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense (F44620-70-C-0107) and is monitored by the Air Force Office of Scientific Research.     

Decomposition of linear sequential machines

Linear sequential machines can sometimes be decomposed into parallel and series connections of smaller linear sequential machines. Necessary and sufficient conditions are given for such decompositions to exist for finite linear sequential machines.Research sponsored by the Air Force Office of Scientific Research, Grant AF-AFOSR 639-67, and by the National Science Foundation, Grant GP-6945     

Decomposition of linear sequential machines. II

Linear sequential machines can sometimes be decomposed into parallel or series connections of smaller linear sequential machines. Necessary and sufficient conditions for the existence of such decompositions are given for finite linear sequential machines with and without state-splitting.Research sponsored by the Air Force Office of Scientific Research Grant AF-AFOSR 639–67.     

Solution of sparse positive definite systems on a shared-memory multiprocessor

Algorithms and software for solving sparse symmetric positive definite systems on serial computers have reached a high state of development. In this paper, we present algorithms for performing sparse Cholesky factorization and sparse triangular solutions on a shared-memory multiprocessor computer, along with some numerical experiments demonstrating their performance on a Sequent Balance 8000 system.Research was supported by the Applied Mathematical Sciences Research Program of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marieta Energy Systems, Inc., by the U.S. Air Force Office of Scientific Research under contract AFOSR-ISSA-85-00083 and by the Canadian Natural Sciences and Engineering Research Council under grants A8111 and A5509.     

A complete axiomatic semantics of spawning

Summary In modern imperative languages there are two commonly occurring ways to activate concurrently running tasks,splitting (cobegin...coend) andspawning. The programming language Ada makes use of both forms of task activation. We present a formal system for verifying partial correctness specifications of Ada tasks activated by spawning. The system is based upon a view of tasks as histories of events. We show how the mindset of splitting may be applicable when developing a formal system for reasoning about spawning. The resultant proof system is compositional, and a robust extension of partial correctness proof systems for sequential constructs. A transition model is given for spawning, and the proof system is proven complete in the sense of Cook [10] relative to this model, under certain reasonable assumptions. The specific proof rules given apply to a subset of Ada without real-time and distributed termination. Our approach to task verification applies to other imperative languages besides Ada, and the essential parts of our methodology are applicable to other formal systems besides those based on partial correctness reasoning. Sigurd Meldal is professor of informatics at the University of Bergen. He is interested in techniques and tools based on formal methods for development of concurrent software. His current foci are the investigation of algebraic approaches to nondeterminism, and the participation in the design of a concurrent specification, prototyping and implementation language. The latter supplements formal proof with support for run time control of consistency between concurrent systems as specified and as implemented. Meldal received his cand. real. (1982) and dr. scient. (1986) degrees in informatics from the University of Oslo.This research was supported by a grant from the Norwegian Research Council for Science and the Humanities, by the Defense Advanced Research Projects Agency/Information Systems Technology Office under the office of Naval Research contract N00014-90-J1232, by the Air Force Office of Scientific Research under Grant AFOSR83-0255 and by a Fulbright Scholarship from the US Educational Foundation in Norway     

Tolerating malicious gossip

A new class of gossip protocols to diffuse updates securely is presented. The protocols rely on annotating updates with the path along which they travel. To avoid a combinatorial explosion in the number of annotated updates, rules are employed to choose which updates to keep. Different sets of rules lead to different protocols. Results of simulated executions for a collection of such protocols are described – the protocols would appear to be practical, even in large networks. Received: October 2001 / Accepted: July 2002 Supported in part by ARPA/RADC grant F30602-96-1-0317, AFOSR grant F49620-00-1-0198, Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory Air Force Material Command USAF under agreement number F30602-99-1-0533, National Science Foundation Grant 9703470, and a grant from Intel Corporation. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of these organizations or the U.S. Government.     

Characterizing crossover in genetic algorithms

We characterize crossover and schemata; crossover is a binary operator that preserves schemata and commutes with addition and projection. Moreover, for any setS of chromosomes and familyF of crossover operators, we fully characterize the reachable chromosomes.Research sponsored in part by the Air Force Office of Scientific Research and Office of Naval Research (F49620-90-C-0033), and by the National Science Foundation (IRI-8917545).     

Degradation reduction in optics imagery using Toeplitz structure

This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which involves the removal or minimization of degradations caused by noise and blur in an image, resulting from, in this case, imaging through a medium. Our work here concerns the use of the underlying Toeplitz structure of such problems, and associated techniques for accelerating the convergence of iterative image restoration computations. Denoising methods, including total variation minimization, followed by segmentation-based preconditioning methods for minimum residual conjugate gradient iterations, are investigated. Regularization is accomplished by segmenting the image into (smooth) segments and varying the preconditioners across the segments. By taking advantage of the Toeplitz structure, our algorithms can be implemented with computational complexity of onlyO (ln ² logn), wheren ² is the number of pixels in the image andl is the number of segments used. Also, parallelization is straightforward. Numerical tests are reported for atmospheric imaging problems, including the case of spatially varying blur. Research supported in part by a National Science Foundation Postdoctoral Research Fellowship. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-1039. Research sponsored by the U.S. Air Force Office of Scientific Research under grant F49620-97-1-0139, and by the National Science Foundation under grant CCR-96-23356. Research sponsored by the National Science Foundation under grant CCR-96-23356.     

Boolean Functions as Models for Quantified Boolean Formulas

In this paper, we introduce the notion of models for quantified Boolean formulas. For various classes of quantified Boolean formulas and various classes of Boolean functions, we investigate the problem of determining whether a model exists. Furthermore, we show for these classes the complexity of the model checking problem, which is to check whether a given set of Boolean functions is a model for a formula. For classes of Boolean functions, we establish some characterizations in terms of classes of quantified Boolean formulas that have such a model. This research has been supported in part by the Air Force Office of Scientific Research under grant FA9550-06-1-0050. This research has been supported in part by the NSFC under grants 60573011 and 10410638.