umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Extended Uniformly Limited T0L Languages and Mild Context-Sensitivity
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Institut fuer Informatik, Universität Giessen.
Institut fuer Informatik, Universität Giessen.
2016 (English)In: Eight Workshop on Non-Classical Models of Automata and Applications (NCMA 2016): Short Papers / [ed] Henning Bordihn, Rudolf Freund, Benedek Nagy, and György Vaszil, Wien: Institut für Computersprachen , 2016, 35-46 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study the fixed membership problem for k-uniformly-limited and propagating ET0L systems (kulEPT0L systems). To this end, the algorithm given in [7] is applied. It follows that kulEPT0L languages are parsable in polynomial time. Since kulEPT0L languages are semi-linear [1] and kulEPT0L systems generate certain non-context-free languages, which capture the non-context-free phenomena occurring in natural languages, this is the last building block to show that kulEPT0L languages, for k ≥ 2, belong to the family of mildly context-sensitive languages.

Place, publisher, year, edition, pages
Wien: Institut für Computersprachen , 2016. 35-46 p.
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:umu:diva-125175ISBN: 978-3-200-04725-9 (print)OAI: oai:DiVA.org:umu-125175DiVA: diva2:959486
Conference
Eighth Workshop on Non-Classical Models of Automata and Applications(NCMA 2016)
Available from: 2016-09-07 Created: 2016-09-07 Last updated: 2017-01-20Bibliographically approved

Open Access in DiVA

fulltext(781 kB)32 downloads
File information
File name FULLTEXT01.pdfFile size 781 kBChecksum SHA-512
7c5476fa12f8002dcc50f28bce8179558e65c5d10ded9c2aab7e802e48be3518646b844b5b68b60a30705bb6abd614d94861d2e6483a242798d04c269bcfb7c0
Type fulltextMimetype application/pdf

Other links

URL

Search in DiVA

By author/editor
Bensch, Suna
By organisation
Department of Computing Science
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 32 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 498 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf