NDLI: Towards an algebraic theory of recursion

Content Provider	ACM Digital Library
Author	Ioannidis, Yannis E. Wong, Eugene
Copyright Year	1991
Abstract	An algebraic framework for the study of recursion has been developed. For immediate linear recursion, a Horn clause is represented by a relational algebra operator. It is shown that the set of all such operators forms a closed semiring. In this formalism, query answering corresponds to solving a linear equation. For the first time, the query answer is able to be expressed in an explicit algebraic form within an algebraic structure. The manipulative power thus afforded has several implications on the implementation of recursive query processing algorithms. Several possible decompositions of a given operator are presented that improve the performance of the algorithms, as well as several transformations that give the ability to take into account any selections or projections that are present in a givin query. In addition, it is shown that mutual linear recursion can also be studied within a closed semiring, by using relation vectors and operator matrices. Regarding nonlinear recursion, it is first shown that Horn clauses always give rise to multilinear recursion, which can always be reduced to bilinear recursion. Bilinear recursion is then shown to form a nonassociative closed semiring. Finally, several sufficient and necessary-and-sufficient conditions for bilinear recursion to be equivalent to a linear one of a specific form are given. One of the sufficient conditions is derived by embedding to bilinear recursion in an algebra.
Starting Page	329
Ending Page	381
Page Count	53
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/103516.103521
Journal	Journal of the ACM (JACM)
Volume Number	38
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1991-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Note Concerning the Algebraic Theory of Automata

Alpha-structural recursion and induction

The Complexity of Finite Memory Programs with Recursion

Dynamic Programming as Graph Searching: An Algebraic Approach

Solving Linear Algebraic Equations on an MIMD Computer

Iterated Limiting Recursion and the Program Minimization Problem

Algebraic laws for nondeterminism and concurrency

An Overview of the Theory of Computational Complexity

Solution of Algebraic and Transcendental Equations on an Automatic Digital Computer

Towards an algebraic theory of recursion

Similar Documents

Note Concerning the Algebraic Theory of Automata

Alpha-structural recursion and induction

The Complexity of Finite Memory Programs with Recursion

Dynamic Programming as Graph Searching: An Algebraic Approach

Solving Linear Algebraic Equations on an MIMD Computer

Iterated Limiting Recursion and the Program Minimization Problem

Algebraic laws for nondeterminism and concurrency

An Overview of the Theory of Computational Complexity

Solution of Algebraic and Transcendental Equations on an Automatic Digital Computer

Towards an algebraic theory of recursion