State maps of general behaviors, their lattice structure and bisimulations

A. Agung Julius, Arjan van der SchaftUniversity 2004

Abstract: In this paper we study the so called state maps in the behavioral approach to systems theory. The discussion in this paper continues some preliminary development presented in [5] and it also can be thought of as a generalization of the work in [10]. The concept of states or state variables is present in almost all branches of dynamical systems.

Introduction

In classical systems theory, the concept of "state" often feels like a lucky coincidence that appears across different domains—from discrete automata to continuous-time differential equations. However, these fields often use different languages to describe system equivalence. This paper addresses two main challenges: rigorously constructing "states" directly from system trajectories (the behavioral point of view) and defining "bisimulation" for any general dynamical system, regardless of whether it is discrete, continuous, or hybrid.

The Lattice of State Maps

The paper operates within the behavioral approach, where a system is defined simply by its trajectories over time. The authors define a state map as a function that takes a trajectory and a point in time and maps it to a "state."

A key finding is that these maps follow a partial ordering: one map is "smaller" than another if it collapses more trajectories into the same state while still maintaining the "state property" (capturing all necessary information for the future). Because of this ordering, state maps form a structured lattice. This allows the identification of "maximal" maps (which remember everything) and "minimal" maps (the most efficient representations).

The lattice structure of state maps, illustrating the relationship between maximal, minimal, and canonical constructions.

Generalized Bisimulation

The authors define both time-dependent and time-independent bisimulation relations. Unlike standard definitions tied to specific state-space equations, these are defined over general behaviors. To handle time-independent systems (like those that can be time-shifted), they introduce a "rooted" version of bisimulation to ensure that equivalent systems actually produce the same external observations.

A 2D planar lattice diagram highlighting specific state constructions and their relationships within the behavioral framework.

Key Insights and Results

  • The Lattice of States: The search for a "minimal state space" is not just a heuristic; it is a traversal of a mathematically defined lattice. If a "canonical minimal state map" exists, it sits at a specific point in this lattice.
  • Bisimulation vs. External Behavior: The authors prove that bisimilarity is a stronger condition than just having the same external behavior. Two systems might look the same from the outside but fail to be bisimilar if their internal state-branching structures differ.
  • Consistent Reduction: If two systems are bisimilar, you can "reduce" their state maps (move down the lattice) and they will remain bisimilar, provided the maps are Markovian and past-induced.
  • Theorem 3.9 & 4.6: The authors demonstrate that for "complete" behaviors, time-dependent bisimilarity strictly implies that the systems share the same external behavior. Conversely, if two systems have the same external behavior and admit a "minimal canonical state map," they are guaranteed to be bisimilar.

Limitations and Future Work

The results rely on the assumption that behaviors are "complete" (distinguishable over finite intervals) or that the time axis has a minimal element. This might exclude certain exotic or infinite-horizon systems. Furthermore, the 2D planar lattice diagrams used for visualization are simplified "portraits" and do not capture the full complexity of high-dimensional state map relations.

Future work suggests extending this framework to more complex hybrid systems where discrete jumps and continuous flows interact, using the lattice structure to find the simplest possible hybrid state representation.

Summary updated

Abstract

In this paper we study the so called state maps in the behavioral approach to systems theory. The discussion in this paper continues some preliminary development presented in [5] and it also can be thought of as a generalization of the work in [10]. The concept of states or state variables is present in almost all branches of dynamical
BibTeX
@inproceedings{julius2004state,
  author = {A. Agung Julius and Arjan van der Schaft},
  title = {{State maps of general behaviors, their lattice structure and bisimulations}},
  booktitle = {University},
  year = {2004},
}
Figure