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 条

[1] An Infinitary Affine Lambda-Calculus Isomorphic to the Full Lambda-Calculus
Mazza, Damiano
2012 27TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2012, : 471 - 480
[2] The differential lambda-calculus
Ehrhard, T
Regnier, L
THEORETICAL COMPUTER SCIENCE, 2003, 309 (1-3) : 1 - 41
[3] Lambda-calculus with director strings
Fernández, M
Mackie, I
Sinot, FR
APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2005, 15 (06) : 393 - 437
[4] Spinal Atomic Lambda-Calculus
Sherratt, David
Heijltjes, Willem
Gundersen, Tom
Parigot, Michel
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2020, 2020, 12077 : 582 - 601
[5] A linear linear lambda-calculus
Diaz-Caro, Alejandro
Dowek, Gilles
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2024, : 1103 - 1137
[6] Development Separation in Lambda-Calculus
Xi, Hongwei
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2006, 143 : 207 - 221
[7] A lambda-calculus for dynamic binding
Dami, L
THEORETICAL COMPUTER SCIENCE, 1998, 192 (02) : 201 - 231
[8] EXTENDING THE LAMBDA-CALCULUS WITH UNBIND AND REBIND
Dezani-Ciancaglini, Mariangiola
Giannini, Paola
Zucca, Elena
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2011, 45 (01): : 143 - 162
[9] Two-level Lambda-calculus
Gabbay, Murdoch J.
Mulligan, Dominic P.
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 246 : 107 - 129
[10] SEMANTICS OF TYPED LAMBDA-CALCULUS WITH CONSTRUCTORS
Petit, Barbara
LOGICAL METHODS IN COMPUTER SCIENCE, 2011, 7 (01)

← 1 2 3 4 5 →