13
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      How big is BCI fragment of BCK logic

      Preprint

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We investigate quantitative properties of BCI and BCK logics. The first part of the paper compares the number of formulas provable in BCI versus BCK logics. We consider formulas built on implication and a fixed set of \(k\) variables. We investigate the proportion between the number of such formulas of a given length \(n\) provable in BCI logic against the number of formulas of length \(n\) provable in richer BCK logic. We examine an asymptotic behavior of this fraction when length \(n\) of formulas tends to infinity. This limit gives a probability measure that randomly chosen BCK formula is also provable in BCI. We prove that this probability tends to zero as the number of variables tends to infinity. The second part of the paper is devoted to the number of lambda terms representing proofs of BCI and BCK logics. We build a proportion between number of such proofs of the same length \(n\) and we investigate asymptotic behavior of this proportion when length of proofs tends to infinity. We demonstrate that with probability 0 a randomly chosen BCK proof is also a proof of a BCI formula.

          Related collections

          Most cited references11

          • Record: found
          • Abstract: not found
          • Article: not found

          Finite Range Random Walk on Free Groups and Homogeneous Trees

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            The Wiener Index of simply generated random trees

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Coloring rules for finite trees, and probabilities of monadic second order sentences

              Alan Woods (1997)
                Bookmark

                Author and article information

                Journal
                1112.0643

                Theoretical computer science
                Theoretical computer science

                Comments

                Comment on this article