THE BASIS DECISION PROBLEM IN LAMBDA-CALCULUS

被引：0

作者：

INTRIGILA, B ^{[1
]}

机构：

[1] UNIV LAQUILA,DIPARTIMENTO MATEMAT PURA & APPLICATA,I-67100 LAQUILA,ITALY

来源：

MATHEMATICAL LOGIC QUARTERLY | 1993年 / 39卷 / 02期

关键词：

LAMBDA-CALCULUS; BASIS DECISION PROBLEM;

D O I：

10.1002/malq.19930390120

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable.

引用

页码：178 / 180

页数：3

共 50 条

[21] LAMBDA(BETA') - A LAMBDA-CALCULUS WITH A GENERALIZED BETA-REDUCTION RULE
OBEROI, S
INFORMATION PROCESSING LETTERS, 1995, 54 (01) : 45 - 53
[22] Backpropagation in the Simply Typed Lambda-Calculus with Linear Negation
Brunel, Alois
Mazza, Damiano
Pagani, Michele
PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL, 2020, 4 (POPL):
[23] Continuous normalization for the lambda-calculus and Godel's T
Aehlig, K
Joachimski, F
ANNALS OF PURE AND APPLIED LOGIC, 2005, 133 (1-3) : 39 - 71
[24] SIMULATION IN THE CALL-BY-NEED LAMBDA-CALCULUS WITH LETREC
Schmidt-Schauss, Manfred
Sabel, David
Machkasova, Elena
PROCEEDINGS OF THE 21ST INTERNATIONAL CONFERENCE ON REWRITING TECHNIQUES AND APPLICATIONS (RTA'10), 2010, 6 : 295 - 310
[25] Recursion-free modular arithmetic in the lambda-calculus
Mackie, Maximilien
INFORMATION PROCESSING LETTERS, 2024, 183
[26] LABEL-SELECTIVE LAMBDA-CALCULUS SYNTAX AND CONFLUENCE
AITKACI, H
GARRIGUE, J
THEORETICAL COMPUTER SCIENCE, 1995, 151 (02) : 353 - 383
[27] Self-Quotation in a Typed, Intensional Lambda-Calculus
Jay, Barry
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2018, 336 : 207 - 222
[28] Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
Baillot, Patrick
De Benedetti, Erika
Della Rocca, Simona Ronchi
INFORMATION AND COMPUTATION, 2018, 261 : 55 - 77
[29] CONFLUENCE OF THE LAMBDA-CALCULUS WITH LEFT-LINEAR ALGEBRAIC REWRITING
MULLER, F
INFORMATION PROCESSING LETTERS, 1992, 41 (06) : 293 - 299
[30] STANDARDIZATION AND CONSERVATIVITY OF A REFINED CALL-BY-VALUE LAMBDA-CALCULUS
Guerrieri, Giulio
Paolini, Luca
Della Rocca, Simona Ronchi
LOGICAL METHODS IN COMPUTER SCIENCE, 2017, 13 (04)

← 1 2 3 4 5 →