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
1987
0 references
complexity of algorithms
0 references
parallel computation
0 references
finite automaton
0 references
0.9240378141403198
0 references
0.7748748064041138
0 references
0.7631398439407349
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