Abstract | ||
---|---|---|
We consider various types of unambiguity for logarithmic space bounded Turingmachines and polynomial time bounded log space auxiliary push-down automata.In particular, we introduce the notions of (general), reach, and strong unambiguity.We demonstrate that closure under complement of unambiguous classes impliesequivalence of unambiguity and "unambiguous fewness". This, as we will show,applies in the cases of reach and strong unambiguity for logspace. Among the manyrelations we... |
Year | DOI | Venue |
---|---|---|
1991 | 10.1007/3-540-54458-5_61 | FCT |
Keywords | Field | DocType |
logarithmic space,polynomial time | Discrete mathematics,Combinatorics,Computer science,Equivalence (measure theory),Turing machine,Pushdown automaton,Time complexity,Logarithmic space,Bounded function | Conference |
Volume | ISSN | ISBN |
529 | 0302-9743 | 3-540-54458-5 |
Citations | PageRank | References |
26 | 1.06 | 19 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gerhard Buntrock | 1 | 200 | 12.15 |
Birgit Jenner | 2 | 247 | 14.47 |
Klaus-Jörn Lange | 3 | 274 | 30.58 |
Peter Rossmanith | 4 | 26 | 1.06 |