Tony: Created page with "''Domain-specific algorithm analysis'' by Tony Sloane Analysis of the run-time complexity of an algorithm begins by abstracting the time taken by basic operations. We then consi..."

2013-05-28T13:25:03Z

Created page with "''Domain-specific algorithm analysis'' by Tony Sloane Analysis of the run-time complexity of an algorithm begins by abstracting the time taken by basic operations. We then consi..."

New page

''Domain-specific algorithm analysis'' by Tony Sloane

Analysis of the run-time complexity of an algorithm begins by abstracting the
time taken by basic operations. We then consider how many times each basic
operation will be performed in terms of some measure of problem size. The
result is a formula that estimates run-time in terms of the basic operation
times and the problem size. Space usage can be analysed in a similar way.

This talk will present some preliminary work that applies this method to the
analysis of domain-specific algorithms. Our goal is to provide a way for
algorithms expressed in domain-specific languages to be compared. We show that
the abstraction of basic operations is mostly pre-determined by the domain and
therefore does not have to be done anew for each algorithm. The analysis of
repetition depends on some properties of domain-specific data and the high-
level operations that are performed on that data.

The main example is a comparison between approaches to name analysis in
programming languages as expressed by an attribute grammar domain-specific
language. We aim to get a clear view of the differences between an approach
that propagates an environment around a syntax tree and one that uses
reference attributes to represent naming information by its declarations.

WG211/M12Sloane - Revision history

Tony: Created page with "''Domain-specific algorithm analysis'' by Tony Sloane Analysis of the run-time complexity of an algorithm begins by abstracting the time taken by basic operations. We then consi..."