The complexity of some decision problems about two-dimensional array grammars
type: Item
instance of: scholarly article
title: The complexity of some decision problems about two-dimensional array grammars
zbMATH Open document ID: 0572.68064
DOI: 10.1016/0020-0255(83)90027-0
author: Kenichi Morita
author: Yasunori Yamamoto
author: Kazuhiro Sugata
published in: Information Sciences
publication date: 1983-01-01T00:00:00Z
review text: The complexity of several decision problems concerning two-dimensional isometric array grammars (IAG) is studied. Because of the two-dimensional and the ''isometric'' properties of IAG, many decision problems become very hard to solve even for regular array grammars (RAG), the lowest subclass of IAG in the Chomsky-like hierarchy. In this paper, it is shown that the membership problems for RAGs and for context-free array grammars (CFAG) are both NP-complete. The emptiness problem and the equivalence problem for RAGs are shown to be undecidable.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3913708
zbMATH Keywords: two-dimensional isometric array grammars
zbMATH Keywords: regular array grammars
zbMATH Keywords: membership problems
zbMATH Keywords: context-free array grammars
zbMATH Keywords: emptiness problem
zbMATH Keywords: equivalence problem
MaRDI profile type: Publication
full work available at URL: 0020-0255(83)90027-0
OpenAlex ID: W2012485375
cites work: Q5592246
cites work: Q5656399
cites work: Q3926078
cites work: Hierarchical Structures and Complexities of Parallel Isometric Languages
description: scientific article; zbMATH DE number 3913708