کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662267 1633523 2009 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Index sets for some classes of structures
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Index sets for some classes of structures
چکیده انگلیسی

For a class K of structures, closed under isomorphism, the index set is the set I(K) of all indices for computable members of K in a universal computable numbering of all computable structures for a fixed computable language. We study the complexity of the index set of class of structures with decidable theories. We first prove the result for the class of all structures in an arbitrary finite nontrivial language. After the complexity is found, we prove similar results for some well-known classes of structures, such as directed graphs, undirected graphs, partial orders and lattices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 157, Issues 2–3, February 2009, Pages 139-147