List of issues > Series «Mathematics». 2011. Vol. 4
The theory of Lists and Σ-definability
We consider two-sorted structures (lists algebras) consisting of a basic set S and a set of lists IS (lists are ordered collections of elements from S ∪ IS) with natural relations and operations such as membership relation, head and tail operations etc. and show that recursively definable functions are Σ-definable in the lists algebras. The recursion is on the length and depth of a list.
1. Гончаров С. С. Замечание об аксиомах списочной надстройки GES / С. С. Гончаров // Логические вопросы теории типов данных. – Новосибирск, 1986. – С. 11–15. –(Вычислительные системы, вып. 114).
2. Гончаров С. С. Σ-программирование / С. С. Гончаров, Д. И. Свириденко // Логико-математические проблемы МОЗ. – Новосибирск, 1985. – С. 3—29. – (Вычислительные системы, вып. 107).
3. Ершов Ю. Л. Определимость и вычислимость / Ю. Л. Ершов // Сибирская школа алгебры и логики. – Новосибирск : Научная книга, 1996.
4. Ершов Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин. – СПб. : Лань, 2004.
5. Малых А.А, Манцивода А.В, Ульянов В.С. Логические архитектуры и объектно-ориентированный подход // Вестник НГУ. Сер. Математика, механика, информатика. – 2009. – Т.9, вып. 3. -– С. 64–85.
6. А.А. Малых, А.В. Манцивода. Объектно-ориентированная дескриптивная логика // Изв. Иркут. гос. ун-та. Сер. Математика.– 2011. – Т.4, № 1. – С. 57–72.
7. J. Barwise. Admissible Sets and Structures. Perspectives in Mathematical Logic, Springer-Verlag Berlin Heidelberg NewYork, 1975.
8. Ershov, Yu.L, Goncharov, S.S., Sviridenko, D.I. Semantic Programming. Information processing, Proc. IFIP 10th World Comput. Congress, Dublin, vol. 10. pp 1093-1100, 1986.