Open AccessOn “simple” undecidable fragments of positive and elementary theories of free semigroups of finite or countable rank
Author(s) -
V. G. Durnev,
О. В. Зеткина,
A. I. Zetkina
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1479/1/012061
Subject(s) - undecidable problem , mathematics , countable set , simple (philosophy) , semigroup , quantifier (linguistics) , rank (graph theory) , decidability , elementary theory , prefix , discrete mathematics , pure mathematics , combinatorics , computer science , philosophy , linguistics , epistemology , artificial intelligence , programming language
We establish algorithmic undecidability of “simple” (with respect to the quantifier-prefix and the quantifier-free part of the formulas) fragments of positive theories of finitely generated semigroups and elementary theory of a free countably generated semigroup.