Marcel Wild
YOU?
Author Swipe
View article: Compression with Wildcards: All Models of a Boolean 2-CNF
Compression with Wildcards: All Models of a Boolean 2-CNF Open
Let W be a finite set which simultaneously serves as the universe of any poset (W, ≤) and as the vertex set of any graph G. Our algorithm, abbreviated All-Independent-Ideals (A-I-I), enumerates all G-independent ideals of (W, ≤). Since eve…
View article: Compression with wildcards: Enumerating specific induced subgraphs, and packing them as well
Compression with wildcards: Enumerating specific induced subgraphs, and packing them as well Open
Various algorithms have been proposed to enumerate all connected induced subgraphs of a graph $G=(V,E)$. As a variation we enumerate all "packings of connected sets", i.e. partitions $Π$ of $V$ with the property that each part of $Π$ induc…
View article: Words that Represent Peace
Words that Represent Peace Open
We used data from LexisNexis to determine the words in news media that best classifies countries as higher or lower peace. We found that higher peace news is characterized by themes of finance, daily actitivities, and health and that lower…
View article: Machine Learning Classification of Peaceful Countries: A Comparative Analysis and Dataset Optimization
Machine Learning Classification of Peaceful Countries: A Comparative Analysis and Dataset Optimization Open
This paper presents a machine learning approach to classify countries as peaceful or non-peaceful using linguistic patterns extracted from global media articles. We employ vector embeddings and cosine similarity to develop a supervised cla…
View article: Classifying Peace in Global Media Using RAG and Intergroup Reciprocity
Classifying Peace in Global Media Using RAG and Intergroup Reciprocity Open
This paper presents a novel approach to identifying insights of peace in global media using a Retrieval Augmented Generation (RAG) model and concepts of Positive and Negative Intergroup Reciprocity (PIR/NIR). By refining the definitions of…
View article: Compression with wildcards: All induced metric subgraphs
Compression with wildcards: All induced metric subgraphs Open
Driven by applications in the natural, social and computer sciences several algorithms have been proposed to enumerate all sets $X\s V$ of vertices of a graph $G=(V,E)$ that induce a {\it connected} subgraph. We offer two algorithms for en…
View article: Advertising finite commutative semigroups
Advertising finite commutative semigroups Open
Every mathematician is familiar with the beautiful structure of finite commutative groups. What is less well known is that finite commutative semigroups also have a neat and well-described structure. We prove this in an efficient fashion. …
View article: Enumerating all minimal hitting sets in polynomial total time
Enumerating all minimal hitting sets in polynomial total time Open
Consider a hypergraph (=set system) $\mathbb{H}$ whose $h$ hyperedges are subsets of a set with w elements. We show that the $R$ minimal hitting sets of $\mathbb{H}$ can be enumerated in polynomial total time $O(Rh^2 w^2)$.
View article: Compression with wildcards: All exact or all minimal hitting sets
Compression with wildcards: All exact or all minimal hitting sets Open
Our objective is the compressed enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author’s best knowledge, the only previous attempt towards compression, due to Toda, is based on binary decision di…
View article: Modular lattices of finite length (Part B)
Modular lattices of finite length (Part B) Open
Part B (of a project involving four Parts) is about "bases of lines", a concept introduced by C. Herrmann and the author in the late 80's. Bases of lines attempt to describe a given modular lattice in a geometric way akin to how projective…
View article: Modular lattices of finite length (Part A)
Modular lattices of finite length (Part A) Open
This is Part A of four Parts dedicated to modular lattices of finite length. It builds on 1992 notes of the author (available on ResearchGate), and in so doing heeds a wish of the late Gian-Carlo Rota. Part A is in fairly final form and ma…
View article: Compression with wildcards: All exact, or all minimal hitting sets
Compression with wildcards: All exact, or all minimal hitting sets Open
Our main objective is the COMPRESSED enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author's best knowledge the only previous attempt towards compression, due to Toda, is based on BDD's and much…
View article: Compression with wildcards: All spanning trees with prescribed vertex-degrees
Compression with wildcards: All spanning trees with prescribed vertex-degrees Open
By processing all minimal cutsets of a graph G, and by using novel wildcards, all spanning trees of G can be compactly encoded. Surprisingly, a 1986 algorithm of Winter seems to achieve (Conjecture 2) exactly the same compression, although…
View article: Compression with wildcards: All spanning trees.
Compression with wildcards: All spanning trees. Open
By processing all minimal cutsets of a graph G, and by using novel wildcards, all spanning trees of G can be compactly encoded. Thus, different from all previous enumeration schemes, the spanning trees are not generated one-by-one. The Mat…
View article: ALLSAT compressed with wildcards: Frequent Set Mining
ALLSAT compressed with wildcards: Frequent Set Mining Open
Like any simplicial complex the simplicial complex of all frequent sets can be compressed with wildcards once the maximal frequent sets (=facets) are known. Namely, the task (a particular kind of ALLSAT problem) is achieved by the author's…
View article: Compression with wildcards: Abstract simplicial complexes
Compression with wildcards: Abstract simplicial complexes Open
Despite the more handy terminology of abstract simplicial complexes SC, in its core this article is about antitone Boolean functions. Given the maximal faces (=facets) of SC, our main algorithm, called Facets-To-Faces, outputs SC in a comp…
View article: ALLSAT compressed with wildcards: Partitionings and face-numbers of simplicial complexes.
ALLSAT compressed with wildcards: Partitionings and face-numbers of simplicial complexes. Open
Given the facets of a finite simplicial complex, we use wildcards to enumerate its faces in compressed fashion. Our algorithm, coded in high-level Mathematica code, compares favorably to the hardwired Mathematica command BooleanConvert (=e…
View article: Finding or counting all shellings of a simplicial complex
Finding or counting all shellings of a simplicial complex Open
The shellability status of previously investigated simplicial complexes with up to 24 facets is settled. In case of shellability the exact number of shellings is determined. Our algorithm merely relies on the facets, and not on additional …
View article: ALLSAT compressed with wildcards. Part 4: An invitation for C-programmers.
ALLSAT compressed with wildcards. Part 4: An invitation for C-programmers. Open
The model set of a general Boolean function in CNF is calculated in a compressed format, using novel wildcards. This method can be explained in very visual ways. Preliminary comparison with existing methods (BDD's and Mathematica's ESOP co…
View article: ALLSAT compressed with wildcards: An invitation for C-programmers
ALLSAT compressed with wildcards: An invitation for C-programmers Open
The model set of a general Boolean function in CNF is calculated in a compressed format, using novel wildcards. This method can be explained in very visual ways. Preliminary comparison with existing methods (BDD's and Mathematica's ESOP co…
View article: An efficient data structure for counting all linear extensions of a\n poset, calculating its jump number, and the likes
An efficient data structure for counting all linear extensions of a\n poset, calculating its jump number, and the likes Open
Achieving the goals in the title (and others) relies on a cardinality-wise\nscanning of the ideals of the poset. Specifically, the relevant numbers\nattached to the k+1 element ideals are inferred from the corresponding numbers\nof the k-e…
View article: An efficient data structure for counting all linear extensions of a poset, calculating its jump number, and the likes
An efficient data structure for counting all linear extensions of a poset, calculating its jump number, and the likes Open
Achieving the goals in the title (and others) relies on a cardinality-wise scanning of the ideals of the poset. Specifically, the relevant numbers attached to the k+1 element ideals are inferred from the corresponding numbers of the k-elem…
View article: Tight embedding of modular lattices into partition lattices: progress and program
Tight embedding of modular lattices into partition lattices: progress and program Open
Representing lattices L by equivalence relations amounts to embed them into the lattice Part(V) of all partitions of a set V, and has a long history. Here we are concerned with MODULAR lattices L and aim for sets V as small as possible, i.…
View article: Tight embedding of modular lattices into partition lattices: progress\n and program
Tight embedding of modular lattices into partition lattices: progress\n and program Open
Representing lattices L by equivalence relations amounts to embed them into\nthe lattice Part(V) of all partitions of a set V, and has a long history. Here\nwe are concerned with MODULAR lattices L and aim for sets V as small as\npossible,…
View article: Compression with wildcards: All k-models of a binary decision diagram
Compression with wildcards: All k-models of a binary decision diagram Open
Given a Binary Decision Diagram $B$ of a Boolean function $φ$ in $n$ variables, it is well known that all $φ$-models can be enumerated in output polynomial time, and in a compressed way (using don't-care symbols). We show that all $N$ many…
View article: Compression with wildcards: All k-models of a BDD
Compression with wildcards: All k-models of a BDD Open
Given a Binary Decision Diagram B of a Boolean function \phi in variables, all N many k-ones models of \phi can be enumerated in time polynomial in n and N and |B|. Using novel wildcards enables a compressed enumeration of these models. Si…
View article: ALLSAT compressed with wildcards. Part 2: All k-models of a BDD.
ALLSAT compressed with wildcards. Part 2: All k-models of a BDD. Open
If f is a Boolean function given by a BDD then it is well known how to calculate the number of models (i.e. bitstrings x with f(x)=1). Let |x| be the number of 1's in x. How to calculate the number of k-models x (i.e. having |x|=k) is less…
View article: ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing the clauses one by one
ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing the clauses one by one Open
We present a novel technique for converting a Boolean CNF into an orthogonal DNF, aka exclusive sum of products. Our method (which will be pitted against a hardwired command from Mathematica) zooms in on the models of the CNF by imposing i…
View article: ALLSAT compressed with wildcards. Part 1: Converting CNF's to orthogonal DNF's.
ALLSAT compressed with wildcards. Part 1: Converting CNF's to orthogonal DNF's. Open
For most algorithms in Boolean logic branching means variable-wise branching. We present the apparently novel technique of clause-wise branching, which is used to solve the ALLSAT problem for arbitrary Boolean functions in CNF format. Spe…