A note on the space complexity of some decision problems for finite automata

✍ Scribed by Tao Jiang; B. Ravikumar

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 533 KB
• Volume: 40
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(05)80006-7

✦ Synopsis

In this note, we establish the space complexity of decision problems (such as membership, nonemptiness and equivalence) for some finite automata. Our study includes 2-way infinite automata with a pebble.