Feasible graphs with standard universe
type: Item
instance of: scholarly article
title: Feasible graphs with standard universe
zbMATH Open document ID: 0938.03065
DOI: 10.1016/S0168-0072(97)00064-X
author: Douglas Cenzer
author: Jeffrey Remmel
published in: Annals of Pure and Applied Logic
publication date: 2000-06-14T00:00:00Z
review text: In the paper under review the authors study the isomorphism problem for recursive graphs. It follows easily from well-known work by Grigorieff that any recursive graph is recursively isomorphic to a p-time structure. The authors proved in a previous paper that there is a p-time directed graph which is not recursively isomorphic to any p-time directed graph with standard universe. In this paper the authors study structural properties of graphs which ensure the existence of a recursive isomorphism with a p-time model having a standard universe. Examples of simple graphs which are not recursively isomorphic to a p-time graph with standard universe are constructed. Conditions are given under which a computable graph is recursively isomorphic to a polynomial-time graph with standard universe. It is shown that any recursive tree is recursively isomorphic to a p-time tree with standard universe and that any recursive equivalence relation is recursively isomorphic to a p-time equivalence relation with standard universe.
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1308085
zbMATH Keywords: recursive graphs
zbMATH Keywords: p-time models
zbMATH Keywords: computable trees
zbMATH Keywords: isomorphism problem
zbMATH Keywords: recursive isomorphism
zbMATH Keywords: recursive tree
zbMATH Keywords: recursive equivalence relation
reviewed by: M. M. Arslanov
MaRDI profile type: Publication
cites work: Polynomial-time versus recursive models
cites work: Polynomial-time Abelian groups
cites work: Recursively presented games and strategies
cites work: Feasible Graphs and Colorings
cites work: Q4850547
cites work: Q4249723
cites work: Q4249365
cites work: Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
cites work: Q5592246
cites work: Q3815528
cites work: Complexity-theoretic algebra. II: Boolean algebras
cites work: Q4035316
cites work: Classical recursion theory. Vol. II
cites work: Q4035317
full work available at URL: s0168-0072(97)00064-x
OpenAlex ID: W1990994850
Recommended article: Some universal graphs
Recommended article: Almost universal graphs
Recommended article: Edge-realizable graphs with universal vertices
Recommended article: Universal and unavoidable graphs
Recommended article: Realizability of graphs
Recommended article: Existence and nonexistence of universal graphs
Recommended article: Feasible Graphs and Colorings
Recommended article: Graph theoretic uncertainty and feasibility
Recommended article: Universal graphs and induced-universal graphs
Recommended article: Universal lines in graphs
description: scientific article; zbMATH DE number 1308085