On DOL systems with immigration

We study DOL systems with immigration. We show that sequence and growth equivalence are decidable. We establish regularity and decidability results concerning degrees of ambiguity. As a consequence of results about subword complexity, we show that regularity and ω-regularity are decidable for languages generated by growing systems.     

The language equivalence problem for HD0L systems having D0L growths

We show that language equivalence is decidable for HD0L systems having D0L growths. By definition, an HD0L system H has D0L growth if the length sequence of H is a D0L length sequence.     

The equivalence problem for real-time strict deterministic pushdown automata

A comparison method is described for a pair of real-time strict deterministic pushdown automata, capable of deciding their equivalence.Translated from Kibernetika, No. 5, pp. 14–25, September–October, 1989.     

The equivalence problem of multidimensional multitape automata

This article considers the equivalence problem of multitape automata with multidimensional tapes, where the motion of the heads is monotone in all directions (no backward motion). It is shown that this problem can be reduced to the equivalence problem of ordinary multitape automata. Some applications of the result are adduced.     

The equivalence problem for deterministic MSO tree transducers is decidable

It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.     

Feedback equivalence for general control systems

We discuss the solution to the problem of local equivalence of control systems with n states and p controls in a neighbourhood of a generic point, under the Lie pseudo-group of local time independent feedback transformations. We have shown earlier that this problem is identical with the problem of simple equivalence of the time optimal variational problem. Here we indicate the way in which this identification may be used to obtain closed loop time critical controls for general systems. We show that the classification of general nonlinear systems depends on the classification of all n−p dimensional affine subspaces of the space of symmetric forms in p variables and that the case of control linear systems depends on the classification of all n−p dimensional affine subspaces of the space of skew forms in p variables. We show that in the latter case the G-structure is the prolongation of one determined by a state space transformation group. We give a complete list of normal forms for control linear systems in the case p=n−1.     

The inverse problem for compartmental systems

The current state of the inverse problem for compartmental systems is reviewed and analyzed in terms of three major phases, viz. model specification, identifiability and parameter estimation. Emphasis is given to a review of identifiability for linear compartmental systems and the need to put identifiability in perspective in the context of the inverse problem.     

The extended equivalence problem for a class of non-real-time deterministic pushdown automata

We propose a new class of non-real-time deterministic pushdown automata (dpda's), named dpda's having the weak segmental property (WSP), and show that the equivalence problem is solvable for two dpda's, one of which is in this class. The equivalence checking algorithm to prove this problem is a further extended direct branching algorithm of Tomita; and with the new skipping step combined with the type B replacement of Oyamaguchi, Inagaki and Honda. The algorithm is still relatively simple. The class of dpda's given above is one of the widest known subclasses of proper dpda's (introduced by Ukkonen); with the decidable extended equivalence problem.This work was supported in part by Grants-in-Aid for Scientific Research Nos. 58550240 and 62550259 from the Ministry of Education, Science and Culture, Japan.Presently with the Ome Works, Toshiba Corporation, Ome, Tokyo 198, Japan.     

On strict system equivalence for multidimensional systems

Strict system equivalence describes the connection between least-order realizations of a transfer function in terms of a general linear constant system (Rosenbrock, H. H., 1970, State-space and Multivariable Theory (London: Nelson)). The paper generalizes this and related results to the case of multidimensional systems, i.e. systems of linear partial difference or differential equations with constant coefficients.     

Decidability of the equivalence problem for deterministic pushdown automata

Decidability of the equivalence problem is proved for deterministic pushdown automata. A comparison algorithm for two automata is described. The main theorem leads to solution of a number of open problems in the theory of program schemes and in formal language theory.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 20–45, September–October, 1992.     

Hardness of equivalence checking for composed finite-state systems

Computational complexity of comparing behaviours of systems composed from interacting finite-state components is considered. The main result shows that the respective problems are EXPTIME-hard for all relations between bisimulation equivalence and trace preorder, as conjectured by Rabinovich (Inf Comput 139(2):111–129, 1997). The result is proved for a specific model of parallel compositions where the components synchronize on shared actions but it can be easily extended to other similar models,   to labelled 1-safe Petri nets. Further hardness results are shown for special cases of acyclic systems.