Inkdot versus Pebble over Two-Dimensional Languages

• INOUE, Atsuyuki

• ITO, Akira

• HIRAISHI, Kunihiko

• INOUE, Katsushi

Abstract

This paper investigates a relationship between inkdot and one-pebble for two-dimensional finite automata (2-fa's). Especially we show that (1) alternating inkdot 2-fa's are more powerful than nondeterministic one-pebble 2-fa's, and (2) there is a set accepted by an alternating inkdot 2-fa, but not accepted by any alternating one-pebble 2-fa with only universal states.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/4692

Journal

• IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences E88-A (5), 1173-1180, 2005-05-01

  電子情報通信学会

Keywords

• inkdot
• pebble
• two-dimensional automata
• nondeterminism
• alternation

Details

• CRID: 1050564287490577536
• NII Article ID: 110003213429
• NII Book ID: AA10826239
• ISSN: 09168508
• Web Site: http://hdl.handle.net/10119/4692
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles