A note on undecidable properties of formal languages

A general set of conditions is given under which a property is undecidable for a family of languages. Examples are given of the application of this result to wellknown families of languages.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 Grant No. AF-AFOSR-1203-67.     

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.     

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.     

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.     

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.     

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.     

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.     

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     

On factoring the polyvariance operator

The minimum phase factorization of bounded Hermitian operators (covariance operators) is an essential ingredient in linear filtering and stochastic control. In a recent article the author studied an analogous class of polynomic filtering and stochastic control problems. The present study uses the concept of a Hilbert scale to establish a minimum phase factorization procedure for the polynomic setting. The linear theory is carried over in its entirety.Supported in part by the US Air Force Office of Scientific Research under Grant No. 78-3500 and the National Science Foundation under Grant 78/8871.     

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.     

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.     

Control problem structure and the numerical solution of linear singular systems

Recently, a general numerical procedure has been developed for solvable systems of singular differential equationsE(t)x′(t)+F(t)x(t)=f(t). This paper shows how to exploit the structure present in many control problems to reduce the computational effort substantially. An example is worked which shows that additional reductions are possible in some cases. This research was supported in part by the Air Force Office of Scientific Research under Grant No. 84-0240.     

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.     

Combining databases with prioritized information

To solve a problem one may need to combine the knowledge of several different experts. It can happen that some of the claims of one or more experts may be in conflict with the claims of other experts. There may be several such points of conflict and any claim may be involved in several different such points of conflict. In that case, the user of the knowledge of experts may prefer a certain claim to another in one conflict-point without necessarily preferring that statement in another conflict-point.Our work constructs a framework within which the consequences of a set of such preferences (expressed as priorities among sets of statements) can be computed. We give four types of semantics for priorities, three of which are shown to be equivalent to one another. The fourth type of semantics for priorities is shown to be more cautious than the other three. In terms of these semantics for priorities, we give a function for combining knowledge from different sources such that the combined knowledge is conflict-free and satisfies all the priorities.Jack Minker and Shekhar Pradhan were supported in part by the National Science Foundation grant IRI-89-16059 and Air Force Office of Scientific Research grant 91-0350. V.S. Subrahmanian was supported in part by Army Research Office grant DAAL-03-92-G-0225, Air Force Office of Scientific Research Grant F49620-93-1-0065, and NSF grant IRI-9109755.     

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     

On the parallel-decomposability of geometric problems

There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n ^1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen >p. The goal we seek is to achieve, when solving a problem of sizen >p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen >p as when solving a problem of sizep.The research of M. J. Atallah was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Jyh-Jong Tsay's research was partially supported by the Office of Naval Research under Contract N00014-84-K-0502, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, and the National Science Foundation under Grant DCR-8451393.     

On minimal splitting subspaces and markovian representations

Given a Hilbert spaceH, letH ₁ andH ₂ be two arbitrary subspaces. The problem of finding all minimal splitting subspaces ofH with respect toH ₁ andH ₂ is solved. This result is applied to the stochastic realization problem. Each minimal stochastic realization of a given vector processy defines a family of state spaces. It is shown that these families are precisely those families of minimal splitting subspaces (with respect to the past and the future ofy) which satisfy a certain growth condition.Research sponsored by the Air Force Office of Scientific Research under Grant No. AFOSR-78-3519.     

Invertibility of Discrete-Event Dynamic Systems

In this paper we consider a class of Discrete-Event Dynamic Systems (DEDS) modeled as finite-state automata in which only some of the transition events are directly observed. An invertible DEDS is one for which it is possible to reconstruct the entire event string from the observation of the output string. The dynamics of invertibility are somewhat complex, as ambiguities in unobservable events are typically resolved only at discrete intervals and, perhaps, with finite delay. A notion of resiliency or error recovery is developed for invertibility, and polynomial-time tests for invertibility and for resilient invertibility, as well as a procedure for the construction of a resilient inverter, are discussed.Research supported by the Air Force Office of Scientific Research under Grant AFOSR-88-0032 and by the Army Research Office under Grant DAAL03-86-K0171. This research was partially done during our stay at the Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Rennes, France, and the second author was also supported by IRISA during this time.     

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.     

Automated Analysis of Fault-Tolerance in Distributed Systems

A method for automated analysis of fault-tolerance of distributed systems is presented. It is based on a stream (or data-flow) model of distributed computation. Temporal (ordering) relationships between messages received by a component on different channels are not captured by this model. This makes the analysis more efficient and forces the use of conservative approximations in analysis of systems whose behavior depends on such inter-channel orderings. To further support efficient analysis, our framework includes abstractions for the contents, number, and ordering of messages sent on each channel. Analysis of a reliable broadcast protocol illustrates the method.Supported in part by NSF under Grant CCR-9876058 and ONR under Grants N00014-99-1-0358, N00014-01-1-0109, and N00014-02-1-0363.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.Some of the material contained herein previously appeared in [32]