NDLI: Complexity of implementations on the level of algebraic specifications

Please wait, while we are loading the content...

Definability in Dynamic Logic

Logics for probabilistic programming (Extended Abstract)

Complete axiomatization of algorithmic properties of program schemes with bounded nondeterministic interpretations

Dynamic algebras and the nature of induction

A decision method for the equivalence of some non-real-time deterministic pushdown automata

On the distribution of independent formulae of number theory

The consistency of "P = NP" and related problems with fragments of number theory

Independence results in Computer Science? (Preliminary Version)

Fast allocation of nearby resources in a distributed system

Local and global properties in networks of processors (Extended Abstract)

Deadlock- and livelock-free packet switching networks

Kraft storage and access for list implementations(Extended Abstract)

Vector execution of flow graphs(Extended Abstract)

A complete axiomatization for a large class of dependencies in relational datatbases

Horn clauses and database dependencies (Extended Abstract)

Dynamically maintaining configurations in the plane (Detailed Abstract)

Detection is easier than computation (Extended Abstract)

On translating a set of rectangles

An optimal solution to a wire-routing problem (preliminary version)

Optimal tree layout (Preliminary Version)

The chip complexity of binary arithmetic

The node cost measure for embedding graphs on the planar grid (Extended Abstract)

An approach to the k paths problem

Isomorphism for graphs embeddable on the projective plane

Isomorphism testing for graphs of bounded genus

A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus

Testing isomorphism of cone graphs(Extended Abstract)

The orbit problem is decidable

Testing polynomials which are easy to compute (Extended Abstract)

The complexity of the equivalence problem for straight-line programs

Complexity of implementations on the level of algebraic specifications

A time-space tradeoff for sorting on a general sequential model of computation

Some connections between nonuniform and uniform complexity classes

On some deterministic space complexity problems

Space-time tradeoffs and first order problems in a model of programs

Graph pebbling with many free pebbles can be difficult

Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations

Time-space tradeoffs for some algebraic problems

Comparative schematology and pebbling with auxiliary pushdowns (Preliminary Version)

An information-theoretic approach to time bounds for on-line computation (preliminary version)

Linear expected-time algorithms for connectivity problems (Extended Abstract)

A shortest-path algorithm with expected time O(n2 log n log* n)

Random matroids

Heuristics for weighted perfect matching

Generalized selection and ranking (Preliminary Version)

Efficient dynamic programming using quadrangle inequalities

Critical path scheduling of task systems with resource and processor constraints (Extended Abstract)

Complexity of implementations on the level of algebraic specifications

Content Provider	ACM Digital Library
Author	Mahr, Bernd Ehrig, Hartmut
Abstract	The aim of this paper is to study implementations of abstract data types and their complexity within the framework of algebraic specifications. An implementation of an abstract data type ADTO by an abstract data type ADT1 is defined on a syntactical and on a semantical level where data and operations of ADTO are simulated by those of ADT1. In order to investigate complexity of implemented operations and to compair different implementations we axiomatically introduce complexity measures for the operations in ADTO with respect to a given implementation of ADTO by ADT1. A most natural interesting class of complexity measures which satisfy our axioms is compatible with time complexity of Turing Machines. This is shown by specification and implementation of timebounded Turing Machines within our algebraic framework and the simulation of a general nondeterministic interpreter for algebraic implementations by a nondeterministic Turing Machine. This relationship allows to show the existence of solutions and of upper and lower bounds for the complexity of a broad class of implementation problems in our sense. A corollary shows that there are algebraic specifications for all those recursive functions which are bounded in time by algebraically specifyable functions. Since the complexity measure for ADTO-operations in a given implementation IMPL1 of ADTO by ADT1 in general depends on the complexity of the ADT1-operations it is possible to substitute the complexity of the ADT1-operations which may be obtained from an implementation IMPL2 of ADT1 by ADT2. On the other hand the composite implementation IMPL3 of ADTO by ADT2 can be constructed and it is shown that the composite complexity of IMPL3 is less or equal to the substituted complexity considered above provided that some natural consistency conditions are satisfied.
Starting Page	281
Ending Page	293
Page Count	13
File Format	PDF
ISBN	0897910176
DOI	10.1145/800141.804676
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1980-04-28
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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