A Proof of Plotkin's Conjecture

• Autorzy: Yinbin L. , Maokang L.
• Języki publikacji: EN

Abstrakty

EN

In 1978, G. Plotkin [7] conjectured that for the three-element truthvalue dcpo T, if k> ω then the function space [T^k → T^k] is not a retract of T^k. In this short paper, we constructively prove a stronger result that if k>ω then the function space [T^k → T^k] is not a retract of the Cartesian product of any family of finite posets. Thus Plotkin's Conjecture is proved to be correct.

Słowa kluczowe

EN

coherent domain; products; retract

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 3
• Strony: 301--306
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Yinbin L.

autor

Maokang L.

• School of Applied Mathematics University of Electronic Science and Technology of China Chengdu 610054, China,

Bibliografia

• [1] Abramsky S., Jung A. : Domain Theory, in: Handbook of Logic in Computer Science (S. Abramsky, D. Gabbay, and T. S. E. Maibaum, Eds.), Vol. 3, Clarendon Press, 1994.
• [2] Amadio R. M., Curien P.-L. : Domains and Lambda-Calculi, Cambridge University Press, 1998.
• [3] Gierz G., Hofmann K. H., Keimel K., Lawson J. D., Mislove M., Scott D. S. : Continuous Lattices and Domains, Cambridge University Press, 2003.
• [4] Jung A. : Cartesian Closed Categories of Domains, vol. 66 of CWI tracts, Centrum voor Wiskunde en Informatica, Amsterdam, 1989.
• [5] Jung A. : The classification of continuous domains, Logic in Computer Science, IEEE Computer Society Press, 1990, 35-40.
• [6] Lawson J., Mislove M. : Domain Theory and Topology, in: Open Problems in Topology (J. Van Mill, G. M. Reed, Eds.), North-Holland, 1990.
• [7] Plotkin G. : T! as a Universal Domain, Journal of Computer and System Sciences, 17(1978), 209-236.
• [8] Sciore E., Tang A. : Admissible coherent cpo's, in: Proceedinds of the 5th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 62, 1978, 440-456.
• [9] Scott D. : Outline of a mathematical theory of computation, in 4th Annual Princeton Conference on International Science and System, 1970, 169-176.
• [10] Scott D. : Continuous Lattices, Lecture Notes in Mathematics, 274, 1972, 97-136.
• [11] Scott D. : Data Types as Lattices, SIAM Journal on Computing, Vol. 5, No. 3, 1976, 522-587.
• [12] Scott D. : Domains for denotational semantics, in: Proceedinds of the 9th International Colloquium on Automata, Language and Programming, Lecture Notes in Computer Science, Vol. 140, Springer-Verlag, Berlin, 1982, 577-613.
• [13] Stoltenberg-Hansen V., Lindstrőm I., Griffor E. R. : Mathematical Theory of Domains, Cambridge University Press, 1994.