New Results on Alternating and Non-Deterministic Two-Dimensional Finite-State Automata

Jarkko Kari and Cristopher Moore

Working Papers from Santa Fe Institute

Abstract: We resolve several long-standing open questions regarding the power of various types of finite-state automata to recognize "picture languages," i.e. sets of two-dimensional arrays of symbols. We show that the languages recognized by 4-way alternating finite-state automata (AFAs) are incomparable to the so-called tiling recognizable languages. Specifically, we show that the set of acyclic directed graphs is AFA-recognizable but not tiling recognizable, while the set of non-acyclic directed graphs is tiling recognizable but not AFA-recognizable. More generally, the complement of an AFA-recognizable language is tiling recognizable, and therefore the AFA-recognizable languages are not closed under complement. We also show that the set of languages recognized by 4-way NFAs is not closed under complement, and that NFAs are more powerful than DFAs, even for languages over one symbol.

Date: 2000-09
References: View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:00-09-051

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().