不适
发表于 2025-3-23 11:02:54
The Costa Rican Human Development Story,gödelization there exist two lambda terms E (self-interpreter) and R (reductor), both having a normal form, such that for every (closed or open) lambda term . E⌈.⌉→. and if . has a normal form ., then R⌈.⌉→⌈.⌉.
INCH
发表于 2025-3-23 17:37:37
https://doi.org/10.1007/978-94-007-3879-9lems, for example “reduction of incompletely specified automata” (in short: RISA), are NLINEAR-complete (consequently, NLINEAR ≠ DLINEAR iff RISA ∉ DLINEAR). That notion probably strengthens NP-completeness since we argue that propositional satisfiability is not NLINEAR-complete.
Verify
发表于 2025-3-23 20:47:18
Algorithmic structuring of cut-free proofs, or tree-like LK-proofs (corresponds to the undecidability of second order unification), (2) undecidable for linear LK.-proofs (corresponds to the undecidability of semi-unification), and (3) decidable for tree-like LK.-proofs (corresponds to a decidable subproblem of semi-unification).
Contort
发表于 2025-3-24 01:44:44
A self-interpreter of lambda calculus having a normal form,gödelization there exist two lambda terms E (self-interpreter) and R (reductor), both having a normal form, such that for every (closed or open) lambda term . E⌈.⌉→. and if . has a normal form ., then R⌈.⌉→⌈.⌉.
博爱家
发表于 2025-3-24 03:57:48
Linear time algorithms and NP-complete problems,lems, for example “reduction of incompletely specified automata” (in short: RISA), are NLINEAR-complete (consequently, NLINEAR ≠ DLINEAR iff RISA ∉ DLINEAR). That notion probably strengthens NP-completeness since we argue that propositional satisfiability is not NLINEAR-complete.
INCH
发表于 2025-3-24 08:06:05
http://reply.papertrans.cn/24/2338/233763/233763_16.png
Palpable
发表于 2025-3-24 13:13:50
http://reply.papertrans.cn/24/2338/233763/233763_17.png
Dna262
发表于 2025-3-24 15:42:16
Recursive inseparability in linear logic, the computations and show how to extract ”finite counter models” from this structure. In that way we get a version of Trakhtenbrots theorem without going through a completeness theorem for propositional linear logic. Lastly we show that the interpolant . in propositional linear logic of a provable
capsaicin
发表于 2025-3-24 22:40:20
http://reply.papertrans.cn/24/2338/233763/233763_19.png
宽敞
发表于 2025-3-24 23:34:06
A self-interpreter of lambda calculus having a normal form,combinator and using only normal forms. To this aim we introduce the notion of a canonical algebraic term rewriting system, and we show that any such system can be interpreted in the lambda calculus by the Böhm — Piperno technique in such a way that strong normalization is preserved. This allows us