Elementary complexity and geometry of interaction (Articolo in rivista)

Type
Label
  • Elementary complexity and geometry of interaction (Articolo in rivista) (literal)
Anno
  • 2001-01-01T00:00:00+01:00 (literal)
Alternative label
  • Baillot, Patrick; Pedicini, Marco (2001)
    Elementary complexity and geometry of interaction
    in Fundamenta informaticae
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Baillot, Patrick; Pedicini, Marco (literal)
Pagina inizio
  • 1 (literal)
Pagina fine
  • 31 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 45 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Elementary complexity and geometry of interaction (literal)
Abstract
  • We introduce a geometry of interaction model given by an algebra of clauses equipped with resolution (following \cite{Girard95d}) which proofs of Elementary Linear Logic can be interpreted into. In order to extend geometry of interaction computation (the so called {\em execution formula}) to a wider class of programs in the algebra than just those coming from proofs, we define a variant of execution (called {\em weak execution}). Its application to any program of clauses is shown to terminate with a bound on the number of steps which is elementary in the size of the program. We establish that weak execution coincides with standard execution on programs coming from proofs. (literal)
Prodotto di
Autore CNR

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it