Change search
ReferencesLink to record
Permanent link

Direct link
On the Parameterized Complexity of Linear Context-Free Rewriting Systems
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
2013 (English)In: Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13), Association for Computational Linguistics, 2013, 21-29 p.Conference paper (Other academic)
Abstract [en]

We study the complexity of uniform membership for Linear Context-Free RewritingSystems, i.e., the problem where we aregiven a string w and a grammar G and areasked whether w ∈ L(G). In particular,we use parameterized complexity theoryto investigate how the complexity dependson various parameters. While we focusprimarily on rank and fan-out, derivationlength is also considered.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2013. 21-29 p.
Keyword [en]
parameterized complexity, linear context-free rewriting system
National Category
Language Technology (Computational Linguistics) Computer Science
Research subject
datorlingvistik; Computer Science
URN: urn:nbn:se:umu:diva-71671ISBN: 978-1-937284-65-7OAI: diva2:625420
13th Meeting on the Mathematics of Language (MoL 13), Sofia, Bulgaria, August 9, 2013
Parameterized Natural Language Parsing
Swedish Research Council, 2011-6080
Available from: 2013-06-04 Created: 2013-06-04 Last updated: 2014-04-29Bibliographically approved
In thesis
1. Complexities of Order-Related Formal Language Extensions
Open this publication in new window or tab >>Complexities of Order-Related Formal Language Extensions
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[sv]
Komplexiteter hos ordnings-relaterade utökningar av formella språk
Abstract [en]

The work presented in this thesis discusses various formal language formalisms that extend classical formalisms like regular expressions and context-free grammars with additional abilities, most relating to order. This is done while focusing on the impact these extensions have on the efficiency of parsing the languages generated. That is, rather than taking a step up on the Chomsky hierarchy to the context-sensitive languages, which makes parsing very difficult, a smaller step is taken, adding some mechanisms which permit interesting spatial (in)dependencies to be modeled.

The most immediate example is shuffle formalisms, where existing language formalisms are extended by introducing operators which generate arbitrary interleavings of argument languages. For example, introducing a shuffle operator to the regular expressions does not make it possible to recognize context-free languages like anbn, but it does capture some non-context-free languages like the language of all strings containing the same number of as, bs and cs. The impact these additions have on parsing has many facets. Other than shuffle operators we also consider formalisms enforcing repeating substrings, formalisms moving substrings around, and formalisms that restrict which substrings may be concatenated. The formalisms studied here all have a number of properties in common.

  1. They are closely related to existing regular and context-free formalisms. They operate in a step-wise fashion, deriving strings by sequences of rule applications of individually limited power.
  2. Each step generates a constant number of symbols and does not modify parts that have already been generated. That is, strings are built in an additive fashion that does not explode in size (in contrast to e.g. Lindenmayer systems). All languages here will have a semi-linear Parikh image.
  3. They feature some interesting characteristic involving order or other spatial constraints. In the example of the shuffle multiple derivations are in a sense interspersed in a way that each is unaware of.
  4. All of the formalisms are intended to be limited enough to make an efficient parsing algorithm at least for some cases a reasonable goal.

This thesis will give intuitive explanations of a number of formalisms fulfilling these requirements, and will sketch some results relating to the parsing problem for them. This should all be viewed as preparation for the more complete results and explanations featured in the papers given in the appendices.

Abstract [sv]

Denna avhandling diskuterar utökningar av klassiska formalismer inom formella språk, till exempel reguljära uttryck och kontextfria grammatiker. Utökningarna handlar på ett eller annat sätt omordning, och ett särskilt fokus ligger på att göra utökningarna på ett sätt som dels har intressanta spatiala/ordningsrelaterade effekter och som dels bevarar den effektiva parsningen som är möjlig för de ursprungliga klassiska formalismerna. Detta står i kontrast till att ta det större steget upp i Chomsky-hierarkin till de kontextkänsliga språken, vilket medför ett svårt parsningsproblem.

Ett omedelbart exempel på en sådan utökning är s.k. shuffle-formalismer. Dessa utökar existerande formalismer genom att introducera operatorer som godtyckligt sammanflätar strängar från argumentspråk. Om shuffle-operator introduceras till de reguljära uttrycken ger det inte förmågan att känna igen t.ex. det kontextfria språket anbn, men det fångar istället vissa språk som inte är kontextfria, till exempel språket som består av alla strängar som innehåller lika många a:n, b:n och c:n. Sättet på vilket dessa utökningar påverkar parsningsproblemet är mångfacetterat. Utöver dessa shuffle-operatorer tas också formalismer där delsträngar kan upprepas, formalismer där delsträngar flyttas runt, och formalismer som begränsar hur delsträngar får konkateneras upp. Formalismerna som tas upp här har dock vissa egenskaper gemensamma.

  1. De är nära besläktade med de klassiska reguljära och kontextfria formalismerna. De arbetar stegvis, och konstruerar strängar genom successiva applikationer av individuellt enkla regler.
  2. Varje steg genererar ett konstant antal symboler och modifierar inte det som redan genererats. Det vill säga, strängar byggs additivt och längden på dem kan inte explodera (i kontrast till t.ex. Lindenmayer-system). Alla språk som tas upp kommer att ha en semi-linjär Parikh-avbildning.
  3. De har någon instressant spatial/ordningsrelaterad egenskap. Exempelvis sättet på vilket shuffle-operatorer sammanflätar annars oberoende deriveringar.
  4. Alla formalismerna är tänkta att vara begränsade nog att det är resonabelt att ha effektiv parsning som mål.

Denna avhandling kommer att ge intuitiva förklaring av ett antal formalismer som uppfyller ovanstående krav, och kommer att skissa en blandning av resultat relaterade till parsningsproblemet för dem. Detta bör ses som förberedande inför läsning av de mer djupgående och komplexa resultaten och förklaringarna i de artiklar som finns inkluderade som appendix.

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2014. 60 p.
Report / UMINF, ISSN 0348-0542 ; 2014:13
complexity, automata, languages, order, shuffle, regular expressions, context-free, mildly context-sensitive, parsing, membership, algorithm analysis
National Category
Computer Science
Research subject
Computer Science
urn:nbn:se:umu:diva-88235 (URN)978-91-7601-047-1 (ISBN)
Public defence
2014-05-21, Naturvetarhuset, N320, Umeå Universitet, Umeå, 13:15 (English)
Available from: 2014-04-30 Created: 2014-04-28 Last updated: 2014-04-30Bibliographically approved

Open Access in DiVA

On the Parameterized Complexity of Linear Context-Free Rewriting Systems(674 kB)135 downloads
File information
File name FULLTEXT02.pdfFile size 674 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Accepted papers, draftThe 13th Meeting on the Mathematics of Language

Search in DiVA

By author/editor
Berglund, MartinBjörklund, HenrikDrewes, Frank
By organisation
Department of Computing Science
Language Technology (Computational Linguistics)Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 135 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: 106 hits
ReferencesLink to record
Permanent link

Direct link