Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
diophantine equation
Matrix Multiplication
Operational Semantics
Polynomial Interpolation
Type Checking
Type Inference
Type System
First Order
Subscribe
Academic
Publications
Polynomial Size Analysis of FirstOrder Shapely Functions
Polynomial Size Analysis of FirstOrder Shapely Functions,10.2168/LMCS5(2:10)2009,Logical Methods in Computer Science,Olha Shkaravska,Marko C. J. D.
Edit
Polynomial Size Analysis of FirstOrder Shapely Functions
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Olha Shkaravska
,
Marko C. J. D. Van Eekelen
,
Ron Van Kesteren
,
Simona Ronchi Della Rocca
We present a sizeaware
type system
for firstorder shapely function defini tions. Here, a function definition is called shapely when the size of the result is determined exactly by a polynomial in the sizes of the arguments. Examples of shapely function defi nitions may be implementations of
matrix multiplication
and the Cartesian product of two lists. The
type system
is proved to be sound w.r.t. the
operational semantics
of the language. The
type checking
problem is shown to be undecidable in general. We define a natural syntactic restriction such that the
type checking
becomes decidable, even though size polynomials are not necessarily linear or monotonic. Furthermore, we have shown that the typeinference problem is at least semidecidable (under this restriction). We have implemented a procedure that combines runtime testing and typechecking to automatically obtain size dependencies. It terminates on total typable function definitions.
Journal:
Logical Methods in Computer Science  LMCS
, vol. 5, no. 2, pp. 135, 2009
DOI:
10.2168/LMCS5(2:10)2009
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.macs.hw.ac.uk
)
(
www.lmcsonline.org
)
(
www.informatik.unitrier.de
)
(
arxiv.org
)
More »
Citation Context
(1)
...This work builds on our previous research on size analysis [
17
], where we studied polynomial dependencies of the sizes of output data structures (e.g...
...Using the result from [5], we have shown how to generate test data for size analysis of functional programs in [
17
]...
...3.1 LBF Inference: The Basic Method This polynomial interpretation method was already applied to Size Analysis in previous work [
17
, 18]...
Olha Shkaravska
,
et al.
Testbased inference of polynomial loopbound functions
References
(28)
Cost Analysis of Java Bytecode
(
Citations: 63
)
Elvira Albert
,
Puri Arenas
,
Samir Genaim
,
Germán Puebla
,
Damiano Zanardini
Conference:
European Symposium on Programming  ESOP
, pp. 157172, 2007
Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
(
Citations: 33
)
Elvira Albert
,
Puri Arenas
,
Samir Genaim
,
Germán Puebla
Conference:
Static Analysis Symposium/Workshop on Static Analysis  SAS(WSA)
, pp. 221237, 2008
Synthesis of maxplus quasiinterpretations
(
Citations: 29
)
Roberto M. Amadio
Journal:
Fundamenta Informaticae  FUIN
, vol. 65, no. 12, pp. 2960, 2005
Resource control for synchronous cooperative threads
(
Citations: 10
)
Roberto M. Amadio
,
Silvano Dalzilio
Journal:
Theoretical Computer Science  TCS
, vol. 358, no. 23, pp. 229254, 2006
Mobile Resource Guarantees and Policies
(
Citations: 9
)
David Aspinall
,
Kenneth Mackenzie
Conference:
Construction and Analysis of Safe, Secure, and Interoperable Smart Devices  CASSIS
, pp. 1636, 2005
Sort by:
Citations
(2)
Testbased inference of polynomial loopbound functions
(
Citations: 1
)
Olha Shkaravska
,
Rody Kersten
,
Marko C. J. D. van Eekelen
Conference:
Principles and Practice of Programming in Java  PPPJ
, pp. 99108, 2010
Observation of implicit complexity by non confluence
Guillaume Bonfante
Journal:
Electronic Proceedings in Theoretical Computer Science
, vol. 23, pp. 1529, 2010