Linear Data Structures for Storage Allocation in Attribute Evaluators

F.J. Sluiman, Frederik Jan Sluiman

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

10 Downloads (Pure)

Abstract

Practical and theoretical results have been found concerning the use of global storage allocation for the instances of applied occurrences of an attribute. The practical results focus on the necessary and sufficient conditions to decide at evaluator construction time whether an evaluator can allocate the instances of an applied occurrence to a number of global variables, stackes and queues. Checking these conditions takes polynomial time for a simple multi-visit evaluator and exponential time for an absolutely non-circular evaluator. The theoretical results are concerned with the data structures that are required for the global storage allocation of the instances of applied occurrences in simple multi-X evaluators, where X € {pass, sweep, visit}. For this purpose, the general class of basic linear data structures is introduced. This class of data structures can also be used to explore the theoretical possibilities and limitations of storage allocation techniques in domains other than attribute grammars.
Original languageUndefined
Supervisors/Advisors
  • Alblas, H., Advisor
  • Brinksma, Hendrik , Supervisor
  • Nijholt, Antinus , Supervisor
  • Alblas, H., Advisor
Thesis sponsors
Award date1 Mar 2002
Place of PublicationAmsterdam
Publisher
Print ISBNs90-365-1713-3
Publication statusPublished - 1 Mar 2002

Keywords

  • HMI-SLT: Speech and Language Technology
  • EWI-6561
  • IR-58712
  • METIS-207594

Cite this

Sluiman, F. J., & Sluiman, F. J. (2002). Linear Data Structures for Storage Allocation in Attribute Evaluators. Amsterdam: University of Twente.
Sluiman, F.J. ; Sluiman, Frederik Jan. / Linear Data Structures for Storage Allocation in Attribute Evaluators. Amsterdam : University of Twente, 2002. 141 p.
@phdthesis{446395b785a041a297f3e9054a1c2924,
title = "Linear Data Structures for Storage Allocation in Attribute Evaluators",
abstract = "Practical and theoretical results have been found concerning the use of global storage allocation for the instances of applied occurrences of an attribute. The practical results focus on the necessary and sufficient conditions to decide at evaluator construction time whether an evaluator can allocate the instances of an applied occurrence to a number of global variables, stackes and queues. Checking these conditions takes polynomial time for a simple multi-visit evaluator and exponential time for an absolutely non-circular evaluator. The theoretical results are concerned with the data structures that are required for the global storage allocation of the instances of applied occurrences in simple multi-X evaluators, where X € {pass, sweep, visit}. For this purpose, the general class of basic linear data structures is introduced. This class of data structures can also be used to explore the theoretical possibilities and limitations of storage allocation techniques in domains other than attribute grammars.",
keywords = "HMI-SLT: Speech and Language Technology, EWI-6561, IR-58712, METIS-207594",
author = "F.J. Sluiman and Sluiman, {Frederik Jan}",
note = "Imported from HMI",
year = "2002",
month = "3",
day = "1",
language = "Undefined",
isbn = "90-365-1713-3",
publisher = "University of Twente",
address = "Netherlands",

}

Sluiman, FJ & Sluiman, FJ 2002, 'Linear Data Structures for Storage Allocation in Attribute Evaluators', Amsterdam.

Linear Data Structures for Storage Allocation in Attribute Evaluators. / Sluiman, F.J.; Sluiman, Frederik Jan.

Amsterdam : University of Twente, 2002. 141 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Linear Data Structures for Storage Allocation in Attribute Evaluators

AU - Sluiman, F.J.

AU - Sluiman, Frederik Jan

N1 - Imported from HMI

PY - 2002/3/1

Y1 - 2002/3/1

N2 - Practical and theoretical results have been found concerning the use of global storage allocation for the instances of applied occurrences of an attribute. The practical results focus on the necessary and sufficient conditions to decide at evaluator construction time whether an evaluator can allocate the instances of an applied occurrence to a number of global variables, stackes and queues. Checking these conditions takes polynomial time for a simple multi-visit evaluator and exponential time for an absolutely non-circular evaluator. The theoretical results are concerned with the data structures that are required for the global storage allocation of the instances of applied occurrences in simple multi-X evaluators, where X € {pass, sweep, visit}. For this purpose, the general class of basic linear data structures is introduced. This class of data structures can also be used to explore the theoretical possibilities and limitations of storage allocation techniques in domains other than attribute grammars.

AB - Practical and theoretical results have been found concerning the use of global storage allocation for the instances of applied occurrences of an attribute. The practical results focus on the necessary and sufficient conditions to decide at evaluator construction time whether an evaluator can allocate the instances of an applied occurrence to a number of global variables, stackes and queues. Checking these conditions takes polynomial time for a simple multi-visit evaluator and exponential time for an absolutely non-circular evaluator. The theoretical results are concerned with the data structures that are required for the global storage allocation of the instances of applied occurrences in simple multi-X evaluators, where X € {pass, sweep, visit}. For this purpose, the general class of basic linear data structures is introduced. This class of data structures can also be used to explore the theoretical possibilities and limitations of storage allocation techniques in domains other than attribute grammars.

KW - HMI-SLT: Speech and Language Technology

KW - EWI-6561

KW - IR-58712

KW - METIS-207594

M3 - PhD Thesis - Research UT, graduation UT

SN - 90-365-1713-3

PB - University of Twente

CY - Amsterdam

ER -

Sluiman FJ, Sluiman FJ. Linear Data Structures for Storage Allocation in Attribute Evaluators. Amsterdam: University of Twente, 2002. 141 p.