English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A theory for the derivation of on-line algorithms is presented. The algorithms are derived in the Bird-Meertens calculus for program transformations. This calculus provides a concise functional notation for algorithms, and a few powerful theorems for proving equalities of functions. The theory for the derivation of on-line algorithms is illustrated with the derivation of an algorithm for finding palindromes. An on-line linear-time random access machine (RAM) algorithm for finding the longest palindromic substring in a string is derived, For the purpose of finding the longest palindromic substring, all maximal palindromic substrings are computed. The list of maximal palindromes obtained in the computation of the longest palindrome can be used for other purposes such as finding the largest palindromic rectangle in a matrix and finding the shortest partition of a string into palindromes. 1. Introduction. In this paper we present a theory for the derivation of on-line algorithms. The algorithms are derived in the Bird-Meertens calculus for program transformation. This calculus provides a concise functional notation for algo- rithms, and a few powerful theorems for proving equalities of functions. The theorems are used to transform inefficient but clearly correct specifications (which are functional algorithms themselves) into efficient algorithms. Thus, it is necessary to state (and prove) explicitly all the equalities used in the derivation of an algorithm. Most of the functions we use are well known in functional pro- gramming, see I-5). Aspects of the Bird-Meertens calculus are described in 1-23), (2), (3), and (24). For several classes of problems theories can be developed, such as a theory for problems on lists, see (2) and (18), and a theory for problems on matrices, see I-3) and 1-19). In this paper we further develop the theory of lists, in particular the theory of segments (in the literature, a segment is also called a substring or a factor). We prove a number of theorems with which many on-line algorithms for segment problems can be derived. A left-reduction is a function defined on the data type list whose inductive definitional pattern mimics that of the type. We argue that the recursive structure

The derivation of on-line algorithms, with an application to finding palindromes