Shuffled languages: representation and recognition
2013 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 489-490, 1-20 p.Article in journal (Refereed) Published
Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, in other words, how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.
Place, publisher, year, edition, pages
Elsevier, 2013. Vol. 489-490, 1-20 p.
Interleaving, Shuffle languages, Membership problems
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-79714DOI: 10.1016/j.tcs.2013.04.022ISI: 000320973900001OAI: oai:DiVA.org:umu-79714DiVA: diva2:644023
ProjectsParameterized Natural Language Parsing
FunderSwedish Research Council, 621-2011-6080