Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Subcritical pattern ...
Conference paper

Subcritical pattern languages for and/or trees

Jakub Kozik (1)
(1) Theoretical Computer Science Department [Krakow]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Proceedings
DOI
10.46298/dmtcs.3582
License
https://about.hal.science/hal-authorisation-v1
Indicators
598
Views
537
Downloads

Subcritical pattern languages for and/or trees

Jakub Kozik (1)
(1) Theoretical Computer Science Department [Krakow]
Abstract
Let $P_k(f)$ denote the density of and/or trees defining a boolean function $f$ within the set of and/or trees with fixed number of variables $k$. We prove that there exists constant $B_f$ such that $P_k(f) \sim B_f \cdot k^{-L(f)-1}$ when $k \to \infty$, where $L(f)$ denote the complexity of $f$ (i.e. the size of a minimal and/or tree defining $f$). This theorem has been conjectured by Danièle Gardy and Alan Woods together with its counterpart for distribution $\pi$ defined by some critical Galton-Watson process. Methods presented in this paper can be also applied to prove the analogous property for $\pi$.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • And/Or trees
  • probability distribution for Boolean functions
  • tree enumeration
Cited by

Source: OpenCitations

  • Tautologies over implication with negative literals

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Marek Zaionc ORCID

    Journal reference : Volume 56, 2010, pp. 388-396

    DOI : 10.1002/malq.200810053

  • Asymptotic Properties of Combinatory Logic

    Jagiellonian University Repository (Jagiellonian University)

    Authors : Maciej Bendkowski, Katarzyna Grygiel, Marek Zaionc ORCID

    Journal reference : Volume , 2015, pp. 62-72

    DOI : 10.1007/978-3-319-17142-5_7

  • Complexity and Limiting Ratio of Boolean Functions over Implication

    Lecture notes in computer science

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume , 2008, pp. 347-362

    DOI : 10.1007/978-3-540-85238-4_28

  • And/or trees: A local limit point of view

    arXiv (Cornell University)

    Authors : Nicolas Broutin, Cécile Mailler ORCID

    Journal reference : Volume 53, 2018, pp. 15-58

    DOI : 10.1002/rsa.20758

  • Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem

    Authors : Antoine Genitrini ORCID, Cécile Mailler ORCID

    Journal reference : Volume , 2014, pp. 466-477

    DOI : 10.1007/978-3-642-54423-1_41

  • In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid

    Jagiellonian University Repository (Jagiellonian University)

    Authors : Antoine Genitrini ORCID, Jakub Kozik ORCID

    Journal reference : Volume 163, 2011, pp. 875-887

    DOI : 10.1016/j.apal.2011.09.011

  • Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability

    Authors : Antoine Genitrini ORCID, Cécile Mailler ORCID

    Journal reference : Volume 76, 2016, pp. 1106-1138

    DOI : 10.1007/s00453-016-0113-3

  • The fraction of large random trees representing a given Boolean function in implicational logic

    Random Structures and Algorithms

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume 40, 2011, pp. 317-349

    DOI : 10.1002/rsa.20379
Preview
Loading PDF preview...