Universal Horn Sentences and the Joint Embedding Property
Copyright policy )Universal Horn Sentences and the Joint Embedding Property
The finite models of a universal sentence $\Phi$ in a finite relational signature are the age of a structure if and only if $\Phi$ has the joint embedding property. We prove that the computational problem whether a given universal sentence $\Phi$ has the joint embedding property is undecidable, even if $\Phi$ is additionally Horn and the signature of $\Phi$ only contains relation symbols of arity at most two.
- Centrum Wiskunde & Informatica Netherlands
- Dutch Research Council Netherlands
- TU Dresden Germany
- STICHTING CENTRUM VOOR WISKUNDE EN INFORMATICA Netherlands
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, universal Horn sentence, Applications of universal algebra in computer science, Analysis of algorithms and problem complexity, Model theory of finite structures, Undecidability and degrees of sets of sentences, Mathematics - Logic, Joint embedding property, Logic in Computer Science (cs.LO), computer science - logic in computer science, QA1-939, FOS: Mathematics, Horn, mathematics - logic, Logic (math.LO), Universal, Mathematics, joint embedding property
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, universal Horn sentence, Applications of universal algebra in computer science, Analysis of algorithms and problem complexity, Model theory of finite structures, Undecidability and degrees of sets of sentences, Mathematics - Logic, Joint embedding property, Logic in Computer Science (cs.LO), computer science - logic in computer science, QA1-939, FOS: Mathematics, Horn, mathematics - logic, Logic (math.LO), Universal, Mathematics, joint embedding property
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!