ScholarLens Back to search
1991•International Journal of Pattern Recognition and Artificial IntelligenceRequires access

PUZZLE GRAMMARS AND CONTEXT-FREE ARRAY GRAMMARS

Maurice Nivat, A. Saoudi, K. G. Subramanian, Rani Siromoney, Vincent Rajkumar Dare

Open publisher page 33 citations

Abstract

We introduce a new model for generating finite, digitized, connected pictures called puzzle grammars and study its generative power by comparison with array grammars. We note how this model generalizes the classical Chomskian grammars and study the effect of direction-independent rewriting rules. We prove that regular control does not increase the power of basic puzzle grammars. We show that for basic and context-free puzzle grammars, the membership problem is NP-complete and the emptiness problem is undecidable.

About this research paper

What this paper is about

We introduce a new model for generating finite, digitized, connected pictures called puzzle grammars and study its generative power by comparison with array grammars. We note how this model generalizes the classical Chomskian grammars and study the effect of direction-independent rewriting rules. We prove that regular control does not increase the power of basic puzzle grammars. We show that for basic and context-free puzzle grammars, the membership problem is NP-complete and the emptiness problem is undecidable.

Why it matters

OpenAlex reports 33 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We introduce a new model for generating finite, digitized, connected pictures called puzzle grammars and study its generative power by comparison with array grammars. We note how this model generalizes the classical Chomskian grammars and study the effect of direction-independent rewriting rules. We prove that regular control does not increase the power of basic puzzle grammars. We show that for basic and context-free puzzle grammars, the membership problem is NP-complete and the emptiness problem is undecidable.

Key concepts: Tree-adjoining grammar, Embedded pushdown automaton, Context-sensitive grammar, Context-free grammar, Phrase structure grammar, Indexed grammar, Rule-based machine translation, L-attributed grammar

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
PUZZLE GRAMMARS AND CONTEXT-FREE ARRAY GRAMMARS — Research Paper | ScholarLens