eCommons

 

Decidable Pairing Functions

Other Titles

Abstract

In Chapter I of this paper we show that the usual, textbook pairing functions have decidable first-order theories. This will be done by exhibiting an infinite axiomatization of certain pairing functions which we characterize as ``acyclic except for ''. This condition is satisfied by the usual pairing functions. We then use a technique of Ehrenfeucht and Fraisse to show that the decision problem for such a pairing function is effectively reduced to the decision problem for the function restricted to . In contrast to the decidability of the first-order theories of certain pairing functions, we show that the weak second-order and monadic second-order theories of these pairing functions are undecidable. In Chapter II we show how to extend the first-order Ehrenfeucht game to a second-order game. Using this extended game, we show that the monadic second-order theory of an equivalence relation is decidable. Some of the results of Chapter I were announced in [16].

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1972-08

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-136

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record