Computational properties of the logic of partial quasiary predicates
| Autor: | Dmitry Shkatov, Mikhail N. Rybakov |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Predicate logic
Discrete mathematics Reduction (recursion theory) 010102 general mathematics 0102 computer and information sciences 01 natural sciences Decidability Undecidable problem Mathematics::Logic TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Recursively enumerable language 010201 computation theory & mathematics TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Computer Science::Logic in Computer Science Computer Science::Programming Languages 0101 mathematics Mathematics |
| Zdroj: | SAICSIT |
| Popis: | We show that the logic of partial quasiary predicates is undecidable over arbitrary structures and not recursively enumerable over finite structures. The results are obtained by reduction from the classical predicate logic. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|