1. Home
2. Questions
3. Tags
5. Users
6. Jobs
7. Companies
8. Unanswered
Teams

Ask questions, find answers and collaborate at work with Stack Overflow for Teams.
Try Teams for free Explore Teams
Teams
Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Return to Question

edited tags

Link

edited May 22, 2015 at 8:44

user23522

complexity-theory turing-machines context-free space-complexity lower-bounds

Tweeted twitter.com/#!/StackCompSci/status/601429691090731008

occurred May 21, 2015 at 16:49

edited tags; edited title

Link

edited May 21, 2015 at 16:08

72.9k
30
181
393

TM recognizing $\lbrace{0^n1^n | n \geq 0 \rbrace}$$0^n1^n$ requires $\OmegaΩ(\text{log }nn)$ space

complexity-theory turing-machines context-free space-complexity lower-bounds

edited tags

Link

edited May 21, 2015 at 14:21

user23522

turing-machines context-free space-complexity lower-bounds

Source Link

asked May 21, 2015 at 12:54

user23522

Loading