Definability by programs in first-order structures

DOI10.1016/0304-3975(83)90013-0zbMath0499.68009OpenAlexW2088171493MaRDI QIDQ1171876

A. J. Kfoury

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90013-0

zbMATH Keywords

verificationcomputational complexitymodel theoryrelational structurerecursion theoryprogram semanticsrecursive programsdata type specificationflowcharttruth-table propertyunwind propertypebble game

Mathematics Subject Classification ID

Model theory (03C99) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65) Computability and recursion theory (03D99)

Related Items (9)

``During cannot be expressed by ``after ⋮ An infinite pebble game and applications ⋮ Definability by programs in first-order structures ⋮ Program correctness on finite fields ⋮ On approximate and algebraic computability over the real numbers ⋮ Necessary and sufficient conditions for the universality of programming formalisms ⋮ Some questions about expressiveness and relative completeness in Hoare's logic ⋮ Weakly expressive models for Hoare logic ⋮ The unwind property for programs with bounded memory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized galois theory and its application to complexity
• Definability in dynamic logic
• Definability by programs in first-order structures
• An observation on time-storage trade off
• Model theory
• Program schemes, recursion schemes, and formal languages
• On formalised computer programs
• Interpolation theorems for program schemata
• Program Schemes with Pushdown Stores
• Algorithmic properties of structures
• On Classes of Program Schemata

This page was built for publication: Definability by programs in first-order structures