No label defined (Q3787428)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4050939
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4050939

      Statements

      1988
      0 references
      coordination
      0 references
      automata model of non-terminating processes
      0 references
      communication protocols
      0 references
      complex integrated hardware systems
      0 references
      state space
      0 references
      Büchi automata
      0 references
      P-SPACE complete
      0 references
      \(\omega \)-regular languages
      0 references
      0 references
      [For the entire collection see Zbl 0634.00021.] The use of automata to model non-terminating processes such as communication protocols and complex integrated hardware systems is conceptually attractive because it affords a well-understood mathematical model with an established literature. However, it has long been recognized that a serious limitation of the automaton model in this context is the size of the automaton state-space, which grows exponentially with the number of coordinating components in the protocol or system. Since most protocols or hardware systems of interest have many coordinating components, the pure automaton model has been all but dismissed from serious consideration in this context; the enormous size of the ensuring state-space has been thought to render its analysis intractable. The purpose of this paper is to show that this is not necessarily so. It is shown that through exploitation of symmetries and modularity commonly designed into large coordinating systems, an apparently intractable state space may be tested for a regular-language property or ``task'' through examination of a smaller associated state space. The smaller state space is a ``reduction'' relative to the given task, with the property that the original system performs the given task if and only if the reduced system performs a reduced task. Checking the task-performance of the reduced system amounts to testing whether the \(\omega\)-regular language associated with the reduced system is contained in the language defining the reduced task. For a new class of automata defined here, such testing can be performed in time linear in the number of edges of the automaton defining each reduced language. (For Büchi automata, testing language containment is P-SPACE complete.) All \(\omega\)-regular languages may be expressed by this new class of automata.
      0 references

      Identifiers