umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Extended Uniformly Limited T0L Languages and Mild Context-Sensitivity
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Institut fuer Informatik, Universität Giessen.
Institut fuer Informatik, Universität Giessen.
2016 (Engelska)Ingår i: 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, s. 35-46Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Wien: Institut für Computersprachen , 2016. s. 35-46
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:umu:diva-125175ISBN: 978-3-200-04725-9 (tryckt)OAI: oai:DiVA.org:umu-125175DiVA, id: diva2:959486
Konferens
Eighth Workshop on Non-Classical Models of Automata and Applications(NCMA 2016)
Tillgänglig från: 2016-09-07 Skapad: 2016-09-07 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

fulltext(781 kB)88 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 781 kBChecksumma SHA-512
7c5476fa12f8002dcc50f28bce8179558e65c5d10ded9c2aab7e802e48be3518646b844b5b68b60a30705bb6abd614d94861d2e6483a242798d04c269bcfb7c0
Typ fulltextMimetyp application/pdf

Övriga länkar

URL

Personposter BETA

Bensch, Suna

Sök vidare i DiVA

Av författaren/redaktören
Bensch, Suna
Av organisationen
Institutionen för datavetenskap
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 88 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 811 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf