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
Recognizing shuffled languages
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Formal and Natural 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, Published paper (Refereed)
Abstract [en]

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.
Series
Lecture Notes in Computer Science (LNCS), ISSN 0302-9743 ; 6638
Keyword [en]
interleaving, shuffle languages, membership problems
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-41284DOI: 10.1007/978-3-642-21254-3_10ISI: 000308848700010ISBN: 978-3-642-21253-6 (print)OAI: oai:DiVA.org:umu-41284DiVA: diva2:405441
Conference
5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011
Available from: 2011-03-22 Created: 2011-03-22 Last updated: 2017-01-16Bibliographically approved
In thesis
1. Complexities of Parsing in the Presence of Reordering
Open this publication in new window or tab >>Complexities of Parsing in the Presence of Reordering
2012 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

The work presented in this thesis discusses various formalisms for representing the addition of order-controlling and order-relaxing mechanisms to existing formal language models. An immediate example is shuffle expressions, which can represent not only all regular languages (a regular expression is a shuffle expression), but also features additional operations that generate arbitrary interleavings of its argument strings. This defines a language class which, on the one hand, does not contain all context-free languages, but, on the other hand contains an infinite number of languages that are not context-free. Shuffle expressions are, however, not themselves the main interest of this thesis. Instead we consider several formalisms that share many of their properties, where some are direct generalisations of shuffle expressions, while others feature very different methods of controlling order. Notably all formalisms that are studied here

  • have a semi-linear Parikh image,
  • are structured so that each derivation step generates at most a constant number of symbols (as opposed to the parallel derivations in for example Lindenmayer systems),
  • feature interesting ordering characteristics, created either by derivation steps that may generate symbols in multiple places at once, or by multiple generating processes that produce output independently in an interleaved fashion, and
  • are all limited enough to make the question of efficient parsing an interesting and reasonable goal.

This vague description already hints towards the formalisms considered; the different classes of mildly context-sensitive devices and concurrent finite-state automata.

This thesis will first explain and discuss these formalisms, and will then primarily focus on the associated membership problem (or parsing problem). Several parsing results are discussed here, and the papers in the appendix give a more complete picture of these problems and some related ones.

Place, publisher, year, edition, pages
Umeå: Department of Computing Science, Umeå University, 2012. 100 p.
Series
Report / UMINF, ISSN 0348-0542 ; 12.10
Keyword
parsing, membership problems, complexity theory, reordering, shuffle, mildly context-sensitive, formal languages
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-54643 (URN)978-91-7459-435-5 (ISBN)
Presentation
2012-05-18, Department of Computing Science, 13:00 (English)
Opponent
Supervisors
Available from: 2012-05-29 Created: 2012-05-03 Last updated: 2012-05-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Berglund, MartinBjörklund, HenrikHögberg, Johanna
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 421 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