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
Complexities of Parsing in the Presence of Reordering
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Naturliga och Formella Språk)
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 [en]
parsing, membership problems, complexity theory, reordering, shuffle, mildly context-sensitive, formal languages
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-54643ISBN: 978-91-7459-435-5 (print)OAI: oai:DiVA.org:umu-54643DiVA: diva2:528035
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
List of papers
1. Recognizing Shuffled Languages
Open this publication in new window or tab >>Recognizing Shuffled Languages
2011 (English)Report (Other academic)
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
Umeå: Umeå University, 2011. 29 p.
Series
Report / UMINF, ISSN 0348-0542 ; 11.01
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-54172 (URN)
Available from: 2012-04-17 Created: 2012-04-17 Last updated: 2012-05-29Bibliographically approved
2. Recognizing shuffled languages
Open this publication in new window or tab >>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, 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
Series
Lecture Notes in Computer Science (LNCS), ISSN 0302-9743 ; 6638
Keyword
interleaving, shuffle languages, membership problems
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-41284 (URN)10.1007/978-3-642-21254-3_10 (DOI)000308848700010 ()978-3-642-21253-6 (ISBN)
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
3. The Membership Problem for the Shuffle of Two Deterministic Linear Context-Free Languages is NP-complete
Open this publication in new window or tab >>The Membership Problem for the Shuffle of Two Deterministic Linear Context-Free Languages is NP-complete
2012 (English)Report (Other academic)
Abstract [en]

Formal language models which employ shuffling, or interleaving, of strings are of interest in many areas of computer science. Notable examples include system verification, plan recognition, and natural language processing. Membership problems for the shuffle of languages are especially interesting. It is known that deciding membership for shuffles of regular languages can be done in polynomial time, and that deciding (non-uniform) membership in the shuffle of two deterministic context-free languages is NP-complete. In this paper we narrow the gap by showing that the non-uniform membership problem for the shuffle of two deterministic *linear* context-free languages is NP-complete.

Place, publisher, year, edition, pages
Umeå: Department of Computing Science, Umeå University, 2012. 10 p.
Series
Report / UMINF, ISSN 0348-0542 ; 12.09
Keyword
shuffle, reordering, complexity, membership problems
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-54163 (URN)
Available from: 2012-04-18 Created: 2012-04-17 Last updated: 2012-05-29Bibliographically approved
4. Analyzing Edit Distance on Trees: Tree Swap Distance is Intractable
Open this publication in new window or tab >>Analyzing Edit Distance on Trees: Tree Swap Distance is Intractable
2011 (English)In: Proceedings of the Prague Stringology Conference 2011 / [ed] Jan Holub and Jan Žďárek, Prague: Prague Stringology Club, Czech Technical University , 2011, 59-73 p.Conference paper, Published paper (Refereed)
Abstract [en]

The string correction problem looks at minimal ways to modify one stringinto another using fixed operations, such as for example inserting a symbol, deleting asymbol and interchanging the positions of two symbols (a “swap”). This has been generalizedto trees in various ways, but unfortunately having operations to insert/deletenodes in the tree and operations that move subtrees, such as a “swap” of adjacent subtrees,makes the correction problem for trees intractable. In this paper we investigatewhat happens when we have a tree edit distance problem with only swaps. We callthis problem tree swap distance, and go on to prove that this correction problem isNP-complete. This suggests that the swap operation is fundamentally problematic inthe tree case, and other subtree movement models should be studied.

Place, publisher, year, edition, pages
Prague: Prague Stringology Club, Czech Technical University, 2011
Keyword
formella språk, träd, omordning, komplexitet, NP.komplett
National Category
Computer Science
Research subject
Computer and Information Science
Identifiers
urn:nbn:se:umu:diva-54158 (URN)000325068600006 ()978-80-01-04870-2 (ISBN)
Conference
16th Prague Stringology Conference (PSC), August 29-31 2011, Prague
Available from: 2012-04-18 Created: 2012-04-17 Last updated: 2017-01-17Bibliographically approved

Open Access in DiVA

fulltext(2538 kB)768 downloads
File information
File name FULLTEXT01.pdfFile size 2538 kBChecksum SHA-512
3539f03a709f8fb8db128f694fda528276219731f74a3498f3523c01174cc445dd1406d6e7c900601408349fd5b6e57d99484e5dc67d0e2a1cdfd0004f8eacf9
Type fulltextMimetype application/pdf

Other links

UMINF 12.10

Search in DiVA

By author/editor
Berglund, Martin
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 768 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

isbn
urn-nbn

Altmetric score

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