arXiv Open Access 2020

Computability by Monadic Second-Order Logic

Joost Engelfriet

Lihat Sumber

Abstrak

A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula in monadic second-order logic. The latter means that the formula defines a set of graphs, in the usual way, such that each "computation graph" in that set determines a pair consisting of an input graph and an output graph.

Topik & Kata Kunci

cs.FL

Penulis (1)

Joost Engelfriet

Format Sitasi

APA MLA BibTeX

Engelfriet, J. (2020). Computability by Monadic Second-Order Logic. https://arxiv.org/abs/2008.12151

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓