No label defined (Q3216145)
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 3881886
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3881886 |
Statements
1984
0 references
finite automata
0 references
simulation of automata
0 references
normed networks
0 references
networks of Mealy automata
0 references
decision problem
0 references
basis
0 references
loop problem
0 references
reachability problem
0 references
0.7093070149421692
0 references
0.7042124271392822
0 references
[For the entire collection see Zbl 0538.00005.] In the theory of normed networks - networks of Mealy automata, where each output-line is connected with at most one input-line and only one signal runs in the net during the computation - the decision problem, whether a finite set of automata forms a basis is still open. A finite set B of finite automata is called to be a basis if for each finite automaton A there exists a net over B simulating A. Now the question is for which problems the property to be a basis does play an important role. For the loop problem - Instance: input x, net N; question: does there exist some state and output with \(x,s_{\vec N}y?\)- complexities as P, NP-complete and PSPACE-complete can occur independent of the property to be a basis. In case of basis sets the reachability problem - Instance: input x, states s, s', output y, net N; question: \(x,s_{\vec N}s',y?\)- is PSPACE-complete, whereas for non-basis sets only polynomially decidable sets are known.
0 references