Rectangles and Squares Recognized by Two-Dimensional Automata

Jarkko Kari and Cristopher Moore

Working Papers from Santa Fe Institute

Abstract: We consider sets of rectangles and squares recognized by deterministic and non-deterministic two-dimensional finite-state automata. We show that NFAs are strictly more powerful than DFAs, even for pictures over a one-symbol alphabet. In the process, we show that the pitcure languages recognized by NFAs are not closed under complement, resolving a long-standing open question. We also show that NFAs can only recognize sets of rectangles from the outside that correspond to simple regular languages. Finally, we show that sets of squares recognized by DFAs can be as sparse as any recursively enumerable set.

Date: 2000-06
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-06-032

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 ().