Complexity of the decidability of the unquantified set theory with a rank operator | Zendy

M. Tetruashvili | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Complexity of the decidability of the unquantified set theory with a rank operator

Author(s) -

M. Tetruashvili

Publication year - 1994

Publication title -

georgian mathematical journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.277

H-Index - 27

eISSN - 1572-9176

pISSN - 1072-947X

DOI - 10.1007/bf02317684

Subject(s) - mathematics , decidability , rank (graph theory) , operator (biology) , set (abstract data type) , discrete mathematics , algebra over a field , combinatorics , pure mathematics , computer science , biochemistry , chemistry , repressor , transcription factor , gene , programming language

The unquantified set theory MLSR containing the symbols ∪, ∖, ≠, ∈,R (R(x) is interpreted as a rank ofx) is considered. It is proved that there exists an algorithm which for any formulaQ of the MLSR theory decides whetherQ is true or not using the spacec|Q|3 (|Q| is the length ofQ).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research