On the use of relational expressions in the design of efficient algorithms: Extended abstract

Seppo Sippu, Eljas Soisalon-Soininen

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review

Sammanfattning

Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (^{–1}), and union (U). The efficient computation of the relation denoted by a rélational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
Originalspråkengelska
Titel på gästpublikationAutomata, Languages and Programming : 12th Colloquium, Nafplion, Greece, July 15-19, 1985
RedaktörerWilfried Brauer
Antal sidor9
UtgivningsortBerlin Heidelberg-New York-Tokyo
FörlagSpringer-Verlag
Utgivningsdatum1985
Sidor456-464
ISBN (tryckt)3-540-15650-X
DOI
StatusPublicerad - 1985
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangInternational Colloquium on Automata, Languages and Programming - Nafplion, Grekland
Varaktighet: 15 jul 198519 jul 1985
Konferensnummer: 12 (ICALP)

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer-Verlag
Volym194

Vetenskapsgrenar

  • 113 Data- och informationsvetenskap

Citera det här