Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Programming with “Big Code” Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Objects in Polynomial Time

verfasst von : Emmanuel Hainry, Romain Péchoux

Erschienen in: Programming Languages and Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A type system based on non-interference and data ramification principles is introduced in order to capture the set of functions computable in polynomial time on OO programs. The studied language is general enough to capture most OO constructs and our characterization is quite expressive as it allows the analysis of a combination of imperative loops and of data ramification scheme based on Bellantoni and Cook’s safe recursion using function algebra.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Quasi-Linearizability is Undecidable
Nächstes Kapitel Programming Techniques for Reversible Comparison Sorts
Literatur
1.
Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Cost analysis of object-oriented bytecode programs. Theoret. Comput. Sci. 413(1), 142–159 (2012)CrossRefMathSciNetMATH
2.
Baillot, P., Terui, K.: Light types for polynomial time computation in lambda-calculus. In: Logic in Computer Science, LICS, pp. 266–275 (2004)
3.
Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the poly-time functions. Comput. Complex. 2, 97–110 (1992)CrossRefMathSciNetMATH
4.
Ben-Amram, A.M., Genaim, S., Masud, A.N.: On the termination of integer loops. In: Kuncak, V., Rybalchenko, A. (eds.) VMCAI 2012. LNCS, vol. 7148, pp. 72–87. Springer, Heidelberg (2012) CrossRef
5.
Cachera, D., Jensen, T., Pichardie, D., Schneider, G.: Certified memory usage analysis. In: Fitzgerald, J.S., Hayes, I.J., Tarlecki, A. (eds.) FM 2005. LNCS, vol. 3582, pp. 91–106. Springer, Heidelberg (2005) CrossRef
6.
Cook, B., Podelski, A., Rybalchenko, A.: Terminator: beyond safety. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 415–418. Springer, Heidelberg (2006) CrossRef
7.
8.
Gulwani, S.: SPEED: symbolic complexity bound analysis. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 51–62. Springer, Heidelberg (2009) CrossRef
9.
Gulwani, S., Mehra, K.K., Chilimbi, T.M.: Speed: precise and efficient static estimation of program computational complexity. In: POPL 2009, pp. 127–139. ACM (2009)
10.
Hainry, E., Marion, J.-Y., Péchoux, R.: Type-based complexity analysis for fork processes. In: Pfenning, F. (ed.) FOSSACS 2013 (ETAPS 2013). LNCS, vol. 7794, pp. 305–320. Springer, Heidelberg (2013) CrossRef
11.
12.
Kersten, R., Shkaravska, O., van Gastel, B., Montenegro, M., van Eekelen, M.C.J.D.: Making resource analysis practical for real-time Java. In: JTRES, pp. 135–144 (2012)
13.
Leivant, D., Marion, J.Y.: Lambda calculus characterizations of poly-time. Fundam. Inf. 19(1/2), 167–184 (1993)MathSciNetMATH
14.
Leivant, D., Marion, J.-Y.: Evolving graph-structures and their implicit computational complexity. In: Fomin, F.V., Freivalds, R.U., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 349–360. Springer, Heidelberg (2013) CrossRef
15.
Marion, J.Y.: A type system for complexity flow analysis. In: Logic in Computer Science, LICS, pp. 123–132 (2011)
16.
Volpano, D., Irvine, C., Smith, G.: A sound type system for secure flow analysis. J. Comput. Secur. 4(2/3), 167–188 (1996)
Metadaten
Titel
Objects in Polynomial Time
verfasst von
Emmanuel Hainry
Romain Péchoux
Copyright-Jahr
2015
Buch
Programming Languages and Systems

Print ISBN: 978-3-319-26528-5

Electronic ISBN: 978-3-319-26529-2

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-26529-2_21