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.7837308049201965
0 references
0.7515674829483032
0 references
0.7274786233901978
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