Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [transitivity]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
48 views

### Does this endomorphism over finite automata have a name?

I found this function that can be applied onto a DFA to produce a DFA. Is there a name for it? Above: A simple DFA over the alphabet $\{0, 1\}$ Below: The resultant DFA over the alphabet $\{0\mathrm{$...
277 views

### Changing a relation to become transitive

Given a binary relation $R$ on a finite set $S$, is there an efficient algorithm to transform $R$ to a transitive relation $R'$ by minimum number of addition or deletion of pairs $(x,y)$ to or from $R$...
• 287
50 views

1k views

### Can someone point out why these directed graphs aren't equivalence relations?

As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
6k views

### in O(n) time: Find greatest element in set where comparison is not transitive

Title states the question. We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal. Key points: Comparison is not transitive (think rock ...
68 views

### Algorithm for getting symetric vertex sets of undirected graph

For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph. My definition of symmetric vertex set is: Let $G$ be a graph with ...
• 325
695 views

### Reflexive transitive closure = (zero or more) Kleene star?

In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position. ...
6k views

### Is transitivity required for a sorting algorithm

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators? Background: A sorting algorithm generally ...
• 271