scientific article; zbMATH DE number 4050939
[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.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787428)