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 条

[31] The Bang Calculus: an untyped lambda-calculus generalizing Call-By-Name and Call-By-Value
Ehrhard, Thomas
Guerrieri, Giulio
PROCEEDINGS OF THE 18TH INTERNATIONAL SYMPOSIUM ON PRINCIPLES AND PRACTICE OF DECLARATIVE PROGRAMMING (PPDP 2016), 2016, : 174 - 187
[32] A SELF-APPLICABLE PARTIAL EVALUATOR FOR THE LAMBDA-CALCULUS - CORRECTNESS AND PRAGMATICS
GOMARD, CK
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1992, 14 (02): : 147 - 172
[33] Package Duplication in Interaction Nets and Weak Head Reduction in the lambda-calculus
Institut de Mathématiques de Luminy, Marseille, France
Electron. Notes Theor. Comput. Sci., 2007, 1 SPEC. ISS. (75-86): : 75 - 86
[34] SIMULATION IN THE CALL-BY-NEED LAMBDA-CALCULUS WITH LETREC, CASE, CONSTRUCTORS, AND SEQ
Schmidt-Schauss, Manfred
Sabel, David
Machkasova, Elena
LOGICAL METHODS IN COMPUTER SCIENCE, 2015, 11 (01)
[35] Equational programming in lambda-calculus via SL-systems .1.
Tronci, E
THEORETICAL COMPUTER SCIENCE, 1996, 160 (1-2) : 145 - 184
[36] M. H. Newman's typability algorithm for lambda-calculus
Hindley, J. Roger
JOURNAL OF LOGIC AND COMPUTATION, 2008, 18 (02) : 229 - 238
[37] Instance-Level Modeling and Simulation Using Lambda-Calculus and Object-Oriented Environments
Merunka, Vojtech
ENTERPRISE AND ORGANIZATIONAL MODELING AND SIMULATION, 2011, 88 : 145 - 158
[38] A calculus of lambda calculus contexts
Bognar, M
De Vrijer, R
JOURNAL OF AUTOMATED REASONING, 2001, 27 (01) : 29 - 59
[39] A Calculus of Lambda Calculus Contexts
Mirna Bognar
Roel de Vrijer
Journal of Automated Reasoning, 2001, 27 : 29 - 59
[40] Godelization in the lambda calculus
Goldberg, M
INFORMATION PROCESSING LETTERS, 2000, 75 (1-2) : 13 - 16

← 1 2 3 4 5 →