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
      [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

      Identifiers