Efficient Algorithms on the Family Associated to an Implicational System
An implication system (IS) on a finite set S is a set of rules called Σ -implications of the kind A →_Σ B, with A,B ⊆ S. A subset X ⊆ S satisfies A →_Σ B when ''A ⊆ X implies B ⊆ X'' holds, so ISs can be used to describe constraints on sets of elements, such as dependency or caus...
Main Authors: | Karell Bertet, Mirabelle Nebut |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2004-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/330/pdf |
Similar Items
-
A new characterization and a recognition algorithm of Lucas cubes
by: Andrej Taranenko
Published: (2013-10-01) -
An optimal permutation routing algorithm on full-duplex hexagonal networks
by: Ignasi Sau, et al.
Published: (2008-01-01) -
1-local 33/24-competitive Algorithm for Multicoloring Hexagonal Graphs
by: Rafal Witkowski, et al.
Published: (2013-11-01) -
The asymmetric leader election algorithm with Swedish stopping: a probabilistic analysis
by: Guy Louchard, et al.
Published: (2012-09-01) -
An expected polynomial time algorithm for coloring 2-colorable 3-graphs
by: Yury Person, et al.
Published: (2011-05-01)