6533b831fe1ef96bd1298ddc

RESEARCH PRODUCT

On the use of relational expressions in the design of efficient algorithms

Eljas Soisalon-soininenSeppo Sippu

subject

Discrete mathematicsEmpty stringParsingRelation (database)Binary relationTransitive closure0102 computer and information sciences02 engineering and technology16. Peace & justicecomputer.software_genre01 natural sciencesExpression (mathematics)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESClosure (mathematics)010201 computation theory & mathematics020204 information systems0202 electrical engineering electronic engineering information engineeringTable (database)computerMathematics

description

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 relational 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.

yearjournalcountryeditionlanguage
2005-11-23
https://doi.org/10.1007/bfb0015771