Journal
ALGEBRA AND LOGIC
Volume 55, Issue 6, Pages 421-435Publisher
SPRINGER
DOI: 10.1007/s10469-017-9416-y
Keywords
locally finite structure; computable structure; structure computable in polynomial time; polynomially categorical structure; weakly polynomially categorical structure
Categories
Funding
- RFBR [14-01-00376]
Ask authors/readers for more resources
It is proved that every computable locally finite structure with finitely many functions has a presentation computable in polynomial time. Furthermore, a structure computable in polynomial time is polynomially categorical iff it is finite. If a structure is computable in polynomial time and locally finite then it is weakly polynomially categorical (i.e., categorical with respect to primitive recursive isomorphisms) iff it is finite.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available