Recognizing shuffled languages
2011 (English)In: Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings / [ed] Adrian-Horia Dediu, Shunsuke Inenaga and Carlos Martín-Vide, Springer Berlin/Heidelberg, 2011, 142-154 p.Conference paper (Refereed)
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, i.e., 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
Springer Berlin/Heidelberg, 2011. 142-154 p.
, Lecture Notes in Computer Science (LNCS), ISSN 0302-9743 ; 6638
interleaving, shuffle languages, membership problems
IdentifiersURN: urn:nbn:se:umu:diva-41284DOI: 10.1007/978-3-642-21254-3ISBN: 978-3-642-21253-6OAI: oai:DiVA.org:umu-41284DiVA: diva2:405441
5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011