Name
Abstract | ||
|---|---|---|
Non-uniform complexity measures arising in Automata and Formal Language Theory are characterized in terms of well-known uniform complexity classes. The initial index of languages is introduced by means of several computational models. It is shown to be closely related to context-free cost, boolean circuits, straight line programs, and Turing machines with sparse oracles and time or space bounds. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1007/BFb0028787 | FCT |
Keywords | Field | DocType |
complexity measure,computer model,complexity class,turing machine,boolean circuits | 2-EXPTIME,PH,Complexity class,Discrete mathematics,Boolean circuit,Sparse language,Circuit complexity,Computer science,Theoretical computer science,Alternating Turing machine,Theory of computation | Conference |
ISBN | Citations | PageRank |
3-540-15689-5 | 4 | 0.58 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Josep Díaz | 2 | 53 | 4.90 |
| Joaquim Gabarro | 3 | 43 | 5.67 |