Average Size of Implicational Bases
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Deriving Theorems in Implicational Linear Logic, Declaratively
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 ProvingThe Birkhoff completion of finite lattices
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
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
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
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