Scattered versus context-sensitive rewriting (Q1115634)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Scattered versus context-sensitive rewriting |
scientific article; zbMATH DE number 4087051
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Scattered versus context-sensitive rewriting |
scientific article; zbMATH DE number 4087051 |
Statements
Scattered versus context-sensitive rewriting (English)
0 references
1989
0 references
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.
0 references
scattered grammars
0 references
scattered rewriting
0 references
context-sensitive rewriting
0 references
context-sensitive languages
0 references
scattered context languages
0 references
0.90471596
0 references
0.8917453
0 references
0 references
0.87587166
0 references
0.86720157
0 references
0 references
