No label defined (Q3773353)

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 4033093
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4033093

      Statements

      0 references
      0 references
      1987
      0 references
      complexity of algorithms
      0 references
      parallel computation
      0 references
      finite automaton
      0 references
      [For the entire collection see Zbl 0616.00013.] The non-uniform deterministic finite automaton (NUDFA) was proposed by the first author and was shown to be equivalent to the bounded-width branching program. Some applications of this model are surveyed, including the result that width 5 branching programs recognize exactly the languages recognizable by polynomial length Boolean formulae (the class \(NC^ 1).\) Then the authors extend this theory, giving the characterization of the power of NUDFA's over nilpotent groups and proving some optimal lower bounds for NUDFA's over certain groups which are solvable but not nilpotent.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references