Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Synthesis of max-plus quasi-interpretations

Amadio R. M.

Fundamenta Informaticae

2005

Vol. 65, nr 1,2

29--60

Quasi-interpretations are a tool to bound the size of the values computed by a first-order functional program (or a term rewriting system) and thus a mean to extract bounds on its computational complexity. We study the synthesis of quasi-interpretations selected in the space of polynomials over the max-plus algebra. We prove that the synthesis problem is NP-hard under various conditions and in NP for the particular case of multi-linear quasi-interpretations when programs are specified by rules of bounded size. We provide a polynomial time algorithm to synthesize homogeneous quasi-interpretations of bounded degree and show how to extend the algorithm to synthesize (general) quasi-interpretations. The resulting algorithm generalizes certain syntactic and type theoretic conditions proposed in the literature to control time and space complexity.

On message deliverability and non-uniform receptivity

Amadio R.M., Boudol G., Lhoussaine C.

Fundamenta Informaticae

2002

Vol. 53, nr 2

105-129

The message deliverability property requires that every emitted message has a chance of being received. In the context of the asynchronous p-calculus, we introduce a discipline of non-uniform receptivity that entails this property. Adopting this discipline requires a style of programming where resources are persistent. We give a general method to transform (in a fully abstract way) a process so that it complies with the discipline.