A programming language for the inductive sets, and applications | Zendy

David Harel | Zendy; Dexter Kozen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A programming language for the inductive sets, and applications

Author(s) -

David Harel,

Dexter Kozen

Publication year - 1982

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/bfb0012779

Subject(s) - computer science , inductive logic programming , programming language , logic programming , datalog , turing , turing machine , first order logic , set (abstract data type) , theoretical computer science , computation

We introduce a programming language IND that generalizes alternating Turing machines to arbitrary first-order structures. We show that IND programs (respectively, everywhere-halting IND programs, loop-free IND programs) accept precisely the inductively definable (respectively, hyperelementary, elementary) relations. We give several examples showing how the language provides a robust and computational approach to the theory of first-order inductive definability. We then show: (1) on all acceptable structures (in the sense of Moschovakis [Mo]), r.e. Dynamic Logic is more expressive than finite-test Dynamic Logic. This refines a separation result of Meyer and Parikh [MP]; (2) IND provides a natural query language for the set of fixpoint queries over a relational database, answering a question of Chandra and Harel [CH2].

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research