Olha Shkaravska

Publications

Displaying 1 - 5 of 5
  • Shkaravska, O., & Van Eekelen, M. (2021). Polynomial solutions of algebraic difference equations and homogeneous symmetric polynomials. Journal of Symbolic Computation, 103, 22-45. doi:10.1016/j.jsc.2019.10.022.

    Abstract

    This article addresses the problem of computing an upper bound of the degree d of a polynomial solution P(x) of an algebraic differ- ence equation of the form Gx)(P(x −τ1), . . . , P(x −τs) + G0(x) = 0 when such P(x) with the coefficients in a field K of character- istic zero exists and where G is a non-linear s-variable polynomial with coefficients in K[x] and G0 is a polynomial with coefficients in K. It will be shown that if G is a quadratic polynomial with constant coefficients then one can construct a countable family of polynomi- als fl(u0) such that if there exists a (minimal) index l0 with fl0(u0) being a non-zero polynomial, then the degree d is one of its roots or d ≤ l0, or d < deg(G0). Moreover, the existence of such l0 will be proven for K being the field of real numbers. These results are based on the properties of the modules generated by special fami- lies of homogeneous symmetric polynomials. A sufficient condition for the existence of a similar bound of the degree of a polynomial solution for an algebraic difference equation with G of arbitrary total degree and with variable coefficients will be proven as well.
  • Kersten, R. W. J., Van Gastel, B. E., Shkaravska, O., Montenegro, M., & Van Eekelen, M. C. J. D. (2014). ResAna: a resource analysis toolset for (real-time) JAVA. Concurrency and Computing: Practice and Experience, 26, 2432-2455. doi:10.1002/cpe.3154.

    Abstract

    For real-time and embedded systems, limiting the consumption of time and memory resources is often an important part of the requirements. Being able to predict bounds on the consumption of such resources during the development process of the code can be of great value. In this paper, we focus mainly on memory-related bounds. Recent research results have advanced the state of the art of resource consumption analysis. In this paper, we present a toolset that makes it possible to apply these research results in practice for (real-time) systems enabling JAVA developers to analyse symbolic loop bounds, symbolic bounds on heap size and both symbolic and numeric bounds on stack size. We describe which theoretical additions were needed in order to achieve this. We give an overview of the capabilities of the RESANA (Radboud University Nijmegen, The Netherlands) toolset that is the result of this effort. The toolset can not only perform generally applicable analyses, but it also contains a part of the analysis that is dedicated to the developers' (real-time) virtual machine, such that the results apply directly to the actual development environment that is used in practice
  • Lenkiewicz, P., Shkaravska, O., Goosen, T., Windhouwer, M., Broeder, D., Roth, S., & Olsson, O. (2014). The DWAN framework: Application of a web annotation framework for the general humanities to the domain of language resources. In N. Calzolari, K. Choukri, T. Declerck, H. Loftsson, B. Maegaard, J. Mariani, A. Moreno, J. Odijk, & S. Piperidis (Eds.), Proceedings of LREC 2014: 9th International Conference on Language Resources and Evaluation (pp. 3644-3649).
  • Shkaravska, O., Van Eekelen, M., & Tamalet, A. (2014). Collected size semantics for strict functional programs over general polymorphic lists. In U. Dal Lago, & R. Pena (Eds.), Foundational and Practical Aspects of Resource Analysis: Third International Workshop, FOPARA 2013, Bertinoro, Italy, August 29-31, 2013, Revised Selected Papers (pp. 143-159). Berlin: Springer.

    Abstract

    Size analysis can be an important part of heap consumption analysis. This paper is a part of ongoing work about typing support for checking output-on-input size dependencies for function definitions in a strict functional language. A significant restriction for our earlier results is that inner data structures (e.g. in a list of lists) all must have the same size. Here, we make a big step forwards by overcoming this limitation via the introduction of higher-order size annotations such that variate sizes of inner data structures can be expressed. In this way the analysis becomes applicable for general, polymorphic nested lists.
  • Shkaravska, O., & Van Eekelen, M. (2014). Univariate polynomial solutions of algebraic difference equations. Journal of Symbolic Computation, 60, 15-28. doi:10.1016/j.jsc.2013.10.010.

    Abstract

    Contrary to linear difference equations, there is no general theory of difference equations of the form G(P(x−τ1),…,P(x−τs))+G0(x)=0, with τi∈K, G(x1,…,xs)∈K[x1,…,xs] of total degree D⩾2 and G0(x)∈K[x], where K is a field of characteristic zero. This article is concerned with the following problem: given τi, G and G0, find an upper bound on the degree d of a polynomial solution P(x), if it exists. In the presented approach the problem is reduced to constructing a univariate polynomial for which d is a root. The authors formulate a sufficient condition under which such a polynomial exists. Using this condition, they give an effective bound on d, for instance, for all difference equations of the form G(P(x−a),P(x−a−1),P(x−a−2))+G0(x)=0 with quadratic G, and all difference equations of the form G(P(x),P(x−τ))+G0(x)=0 with G having an arbitrary degree.

Share this page