×

zbMATH — the first resource for mathematics

Recursive terms in semantic programming. (English. Russian original) Zbl 07035746
Sib. Math. J. 59, No. 6, 1014-1023 (2018); translation from Sib. Mat. Zh. 59, No. 6, 1279-1290 (2018).
Summary: For constructing an enrichment of a language with restricted quantifiers, we extend the notion of term by the construction of the terms conditional and recursive with respect to lists. We show that the so-obtained extension of the language of formulas with restricted quantifiers over structures with hereditary finite lists is a conservative enrichment and the new terms are \({\Delta}\)-definable in the basic language.

MSC:
68N17 Logic programming
68Q55 Semantics in the theory of computing
03B70 Logic in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Goncharov, S. S., Conditional terms in semantic programming, Sib. Math. J., 58, 794-800, (2017) · Zbl 1420.03059
[2] Goncharov, S. S.; Sviridenko, D. I., Σ-Programming, Trans. Amer. Math. Soc., 142, 101-121, (1989) · Zbl 0671.03021
[3] Goncharov, S. S.; Sviridenko, D. I., Σ-Programming and their semantics, Vychisl. Systemy, 120, 24-51, (1987) · Zbl 0696.03014
[4] Goncharov, S. S.; Sviridenko, D. I., Theoretical aspects of Σ-programming, Lect. Notes Comput. Sci., 215, 169-179, (1986) · Zbl 0621.68021
[5] Ershov, Yu. L.; Goncharov, S. S.; Sviridenko, D. I., Semantic programming, Information Processing 86. Proc. IFIP 10th World Comput. Congress, Dublin, 31, 1113-1120, (1986) · Zbl 0606.68011
[6] Goncharov, S. S.; Sviridenko, D. I., Mathematical bases of semantic programming, Soviet Math. Dokl., 31, 608-610, (1986) · Zbl 0643.68015
[7] Ershov, Yu. L.; Goncharov, S. S.; Sviridenko, D. I., Semantic foundations of programming, Lect. Notes Comput. Sci., 278, 116-122, (1987) · Zbl 0642.68029
[8] Ershov, Yu. L., The principle of Σ-enumeration, Soviet Math. Dokl., 27, 670-672, (1983) · Zbl 0539.03016
[9] Ershov, Yu. L., Dynamic logic over admissible sets, Soviet Math. Dokl., 28, 739-742, (1983) · Zbl 0576.68009
[10] Ershov Yu. L., Definability and Computability, Consultants Bureau, New York and London (1996). · Zbl 0870.03019
[11] Goncharov, S. S., The theory of lists, and its models, Vychisl. Systemy, 114, 84-95, (1986) · Zbl 0649.03014
[12] Goncharov, S. S., Data models and languages for their description, Trans. Amer. Math. Soc., 143, 139-152, (1989) · Zbl 0674.68019
[13] Ershov Yu. L., Goncharov S. S., Nerode A., and Remmel J., Introduction to the Handbook of Recursive Mathematics. Vol. 138, Elsevier, Amsterdam (1998). · Zbl 0930.03037
[14] Ershov, Yu. L.; Puzarenko, V. G.; Stukachev, A. I., HF-computability, 169-242, (2011) · Zbl 1260.03086
[15] Morozov, A. S.; Puzarenko, V. G., Σ-subsets of natural numbers, Algebra and Logic, 43, 162-178, (2004) · Zbl 1115.03051
[16] Ospichev, S.; Ponomarev, D., A note on the complexity of formulas in semantic programming, Sib. Elektron. Mat. Izv., 15, 987-995, (2018) · Zbl 1403.03061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.