Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Leftmost derivations ...
Article

Leftmost derivations of propagating scattered context grammars: a new proof

Tomáš Masopust ORCID (1), Jiří Techet (1)
(1) Faculty of Information Technology [Brno]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2008
Last modified on
March 31, 2025
Volume 10
vol. 10:2
Automata, Logic and Semantics
DOI
10.46298/dmtcs.446
License
https://about.hal.science/hal-authorisation-v1
Indicators
1151
Views
675
Downloads

Leftmost derivations of propagating scattered context grammars: a new proof

Tomáš Masopust ORCID (1), Jiří Techet (1)
(1) Faculty of Information Technology [Brno]
Abstract
In 1973, V. Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • An infinite hierarchy of language families generated by scattered context grammars with n-limited derivations

    Theoretical Computer Science

    Authors : Alexander Meduna ORCID, Jiří Techet

    Journal reference : Volume 410, 2008, pp. 1961-1969

    DOI : 10.1016/j.tcs.2008.12.013
Preview
Loading PDF preview...