Change search
ReferencesLink to record
Permanent link

Direct link
The Membership Problem for the Shuffle of Two Deterministic Linear Context-Free Languages is NP-complete
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Naturliga och Formella Språk)
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.
Report / UMINF, ISSN 0348-0542 ; 12.09
Keyword [en]
shuffle, reordering, complexity, membership problems
National Category
Computer Science
URN: urn:nbn:se:umu:diva-54163OAI: diva2:516213
Available from: 2012-04-18 Created: 2012-04-17 Last updated: 2012-05-29Bibliographically 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.
Report / UMINF, ISSN 0348-0542 ; 12.10
parsing, membership problems, complexity theory, reordering, shuffle, mildly context-sensitive, formal languages
National Category
Computer Science
Research subject
Computer Science
urn:nbn:se:umu:diva-54643 (URN)978-91-7459-435-5 (ISBN)
2012-05-18, Department of Computing Science, 13:00 (English)
Available from: 2012-05-29 Created: 2012-05-03 Last updated: 2012-05-29Bibliographically approved

Open Access in DiVA

fulltext(286 kB)104 downloads
File information
File name FULLTEXT02.pdfFile size 286 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

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

Search outside of DiVA

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

Total: 84 hits
ReferencesLink to record
Permanent link

Direct link