Number of quantifiers is better than number of tape cells

1981/06/01 by Neil Immerman · 8 citations
Computer Science · #semigroups and automata theory #Algorithms and Data Compression #Computability, Logic, AI Algorithms

paper · doi:10.1016/0022-0000(81)90039-8

Cited by

• Generalised Reachability Games
• Generalised Reachability Games Revisited
• Who Wins the Multi-Structural Game?
• Pebble Games and Algebraic Proof Systems
• A Game for Counting Logic Formula Size and an Application to Linear Orders
• The model checking fingerprints of CTL operators
• Deciding Parity Games in Quasi-polynomial Time
• Languages which capture complexity classes