Photo by jontyson from unsplash
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… Click to show full abstract
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.
Keywords:
computable polynomial;
structures computable;
polynomial time;
structure
Journal Title: Algebra and Logic
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Algebra and Logic
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!