# Questions tagged [minimization]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
1answer
126 views

### Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

DFA minimization is the problem of transforming a given automaton to an equivalent one with the minimum number of states. Equivalence is taken to be language equivalence. Milner introduced the notion ...
1answer
186 views

2answers
275 views

### Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

Brzozowski's algorithm for converting a DFA into an equivalent minimum-state DFA is remarkably simple: if $R(D)$ denotes the NFA formed by reversing all the edges in a DFA $D$, making the old start ...
0answers
117 views

### Minimize L2 norm by circular permutation

Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that $\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$? Of course one can take all the ...
0answers
126 views

### 3D Bin Packing with one bin with infinite/unknown size

Hi I'm looking for a variation of the Orthogonal 3D-BinPacking algorithm with only one bin of unknown size. I have a set $S$ of $n$ cuboids items $i_j$ with $j=1...n$. The dimensions of the items are ...
0answers
424 views

### Hardness of Minimizing Submodular Functions with Cardinality Constraints

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ). In this introduction, it ...
2answers
481 views

### Does XOR automata (NXA) for finite languages benefit from cycles?

A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA ...
0answers
110 views

### minimal languages that “cover” grammar productions

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
0answers
856 views

### Christofides algorithm for directed graph

Is it possible to implement the Christofides algorithm for an directed Graph? Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to ...
2answers
196 views

### A tool for minimal NFA computation

It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$. As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little ...
0answers
439 views

### Splitting a graph into size constrained clusters

I ran across a problem while working on an algorithm for a game I'm making on the side. It's basically a clustering problem where we have a graph G and want to split it into clusters of equal size ...
1answer
427 views

### Minimizing residual finite state automata

Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular ...
0answers
38 views

### Determine whether a categorical grammar is minimal concerning lexical entries

In order to compare the descriptional complexity of context-free and (combinatoric) categorical I need a way to check if a categorical grammar of a formal language is minimal concerning lexical ...
3answers
422 views

### How to minimize a FSM transducer?

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the ...