Regular approximations through labeled bracketing (revised version)

Show full item record



Permalink

http://hdl.handle.net/10138/33871

Citation

Yli-Jyrä , A M 2003 , Regular approximations through labeled bracketing (revised version) . in G Jaeger , P Monachesi , G Penn & S Wintner (eds) , Unknown host publication . The Conference on Formal Grammar , Vienna , Austria , 16/08/2003 . < http://folli.loria.fr/cds/2003/Workshop/Jaeger/ >

Title: Regular approximations through labeled bracketing (revised version)
Author: Yli-Jyrä, Anssi Mikael
Editor: Jaeger, G.; Monachesi, P.; Penn, G.; Wintner, S.
Contributor: University of Helsinki, Department of Modern Languages 2010-2017
Date: 2003
Language: eng
Number of pages: 14
Belongs to series: Unknown host publication
URI: http://hdl.handle.net/10138/33871
Abstract: This paper presents an approximation method that is based on a new representation theorem for context-free languages. According to it, any context free language can be represented as a homomorphic image of an intersection of a set of constraint languages defining properties of valid labeled bracketings. The intersected languages of the new theorem differ from the ones used in the famous theorem by Chomsky and Schützenberger (1963). If these constraint languages are restricted to make them regular, we obtain a new kind of compact representation for regular approximations. The resulting approximation can be chosen to be either a subset or a superset of the original context-free language
Subject: 113 Computer and information sciences
kontekstittomat kieliopit
keskeisupotus
rajoitukset
approksimointi
sulutukset
context-free grammars
center-embedding
constraints
bracketing
111 Mathematics
homomorfinen esitysmuoto
homomorphic representations
612 Languages and Literature
kieliteknologia
automaattinen jäsentäminen
natural language parsing
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
YliJyra_2003_regappthrlab_mis.pdf 386.4Kb PDF View/Open
YliJyra_2003_regappthrlab_sli.pdf 240.7Kb PDF View/Open
fgvienna.pdf 120.5Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record