paper-with-me

홈 › Papers

Average Size of Implicational Bases

2018-02-12 · Giacomo Kahn, Alexandre Bazin

Implicational bases are objects of interest in formal concept analysis and its applications. Unfortunately, even the smallest base, the Duquenne-Guigues base, has an exponential size in the worst case. In this paper, we use results on the average number of minimal transversals in random hypergraphs to show that the base of proper premises is, on average, of quasi-polynomial size.

📄 PDF Abstract BibTeX arXiv:1802.04032

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Deriving Theorems in Implicational Linear Logic, Declaratively

2020-09-22 · Paul Tarau, Valeria de Paiva

The problem we want to solve is how to generate all theorems of a given size in the implicational fragment of propositional intuitionistic linear logic. We start by filtering for linearity the proof terms associated by o…

Automated Theorem Proving

The Birkhoff completion of finite lattices

2024-05-02 · Mohammad Abdulla, Johannes Hirth, Gerd Stumme

We introduce the Birkhoff completion as the smallest distributive lattice in which a given finite lattice can be embedded as semi-lattice. We discuss its relationship to implicational theories, in particular to R. Wille'…

Efficient Computation of Implicational Universals in Constraint-Based Phonology Through the Hyperplane Separation Theorem

2018-10-01 · WS 2018 10 · Giorgio Magri

This paper focuses on the most basic \textit{implicational universals} in phonological theory, called \textit{T-orders} after Anttila and Andrus (2006). It develops necessary and sufficient constraint characterizations o…

Implicational Universals in Stochastic Constraint-Based Phonology

2018-10-01 · EMNLP 2018 10 · Giorgio Magri

This paper focuses on the most basic implicational universals in phonological theory, called T-orders after Anttila and Andrus (2006). It shows that the T-orders predicted by stochastic (and partial order) Optimality The…

Discriminative Analysis of Linguistic Features for Typological Study

2016-05-01 · LREC 2016 5 · Hiroya Takamura, Ryo Nagata, Yoshifumi Kawasaki

We address the task of automatically estimating the missing values of linguistic features by making use of the fact that some linguistic features in typological databases are informative to each other. The questions to a…

AttributeMissing Values