Interpretation of stream programs: characterizing type 2 polynomial time complexity

Conference object English OPEN
Férée , Hugo; Hainry , Emmanuel; Hoyrup , Mathieu; Péchoux , Romain;
(2010)
  • Publisher: Springer
  • Subject: ACM : F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes/F.1.3.1: Machine-independent complexity | [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]

International audience; We study polynomial time complexity of type 2 functionals. For that purpose, we introduce a first order functional stream language. We give criteria, named well-founded, on such programs relying on second order interpretation that characterize tw... View more
  • References (17)
    17 references, page 1 of 2

    1. Amadio, R.M.: Synthesis of max-plus quasi-interpretations. Fundamenta Informaticae 65(1) (2005) 29-60

    2. Bellantoni, S., Cook, S.A.: A new recursion-theoretic characterization of the polytime functions. Computational complexity 2(2) (1992) 97-110

    3. Bonfante, G., Marion, J.Y., Moyen, J.Y.: Quasi-interpretations. Theor. Comput. Sci.. to appear

    4. Cobham, A.: The Intrinsic Computational Difficulty of Functions. In: Logic, methodology and philosophy of science III, North-Holland Pub. Co. (1965) 24

    5. Constable, R.L.: Type two computational complexity. In: Proc. 5th annual ACM STOC. (1973) 108-121

    6. Endrullis, J., Grabmayer, C., Hendriks, D., Isihara, A., Klop, J.W.: Productivity of stream definitions. Theor. Comput. Sci. 411(4-5) (2010) 765-782

    7. Gaboardi, M., P´echoux, R.: Upper Bounds on Stream I/O Using Semantic Interpretations. In: Computer Science Logic, Springer (2009) 271-286

    8. Irwin, R.J., Royer, J.S., Kapron, B.M.: On characterizations of the basic feasible functionals (Part I). J. Funct. Program. 11(1) (2001) 117-153

    9. Kapron, B.M., Cook, S.A.: A new characterization of type-2 feasibility. SIAM Journal on Computing 25(1) (1996) 117-132

    10. Ko, K.I.: Complexity theory of real functions. Birkhauser Boston Inc. Cambridge, MA, USA (1991)

  • Similar Research Results (1)
  • Metrics
Share - Bookmark