Scattered versus context-sensitive rewriting
type: Item
instance of: scholarly article
title: Scattered versus context-sensitive rewriting
zbMATH Open document ID: 0664.68078
DOI: 10.1007/BF00263503
author: Jakob Gonczarowski
author: Manfred K. Warmuth
published in: Acta Informatica
publication date: 1989-01-01T00:00:00Z
review text: We study the relationship between scattered and context-sensitive rewriting. We prove that an extended version of scattered grammars produces exactly the context-sensitive languages. Also unordered scattered context languages are a proper subset of scattered context languages, and unordered scattered rewriting with erasing does not generate all scattered context (and thus not all context-sensitive) languages.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4087051
zbMATH Keywords: scattered grammars
zbMATH Keywords: scattered rewriting
zbMATH Keywords: context-sensitive rewriting
zbMATH Keywords: context-sensitive languages
zbMATH Keywords: scattered context languages
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00263503
OpenAlex ID: W2011022861
Recommended article: Maximal and Minimal Scattered Context Rewriting
Recommended article: Lazy rewriting and context-sensitive rewriting
Recommended article: Context-sensitive rewriting strategies
Recommended article: From Outermost to Context-Sensitive Rewriting
Recommended article: Applications and extensions of context-sensitive rewriting
Recommended article: Q3696496
Recommended article: Context rewriting
Recommended article: Implementing contextual rewriting
Recommended article: Q3028332
Recommended article: Q4818829
description: scientific article; zbMATH DE number 4087051