Search: onr:"swepub:oai:DiVA.org:umu-54643" >
Complexities of Par...
Complexities of Parsing in the Presence of Reordering
-
- Berglund, Martin, 1981- (author)
- Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
-
- Drewes, Frank, Prof. (thesis advisor)
- Umeå universitet,Institutionen för datavetenskap
-
- Watson, Bruce, Prof. (opponent)
- Department of Information Science, Stellenbosch University (South Africa)
-
(creator_code:org_t)
- ISBN 9789174594355
- Umeå : Department of Computing Science, Umeå University, 2012
- English 100 s.
-
Series: Report / UMINF, 0348-0542 ; 12.10
- Related links:
-
https://www8.cs.umu....
-
show more...
-
https://umu.diva-por... (primary) (Raw object)
-
https://urn.kb.se/re...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- parsing
- membership problems
- complexity theory
- reordering
- shuffle
- mildly context-sensitive
- formal languages
- Computer Science
- datalogi
Publication and Content Type
- vet (subject category)
- lic (subject category)
Find in a library
To the university's database