Questions tagged [minimization]
The minimization tag has no usage guidance.
27
questions
1
vote
1
answer
198
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
CommunityBot
- 1
13
votes
1
answer
444
views
Complexity of NFA to DFA minimization with binary threshold
What is the complexity of the following problem?
Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$?
...
-1
votes
1
answer
88
views
Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?
I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization.
If instead we are given a partial truth table, and we just ...
- 9,595
0
votes
1
answer
199
views
Epsilon-closure and DFA minimization algorithms for probabilistic NFA
Are there any algorithms performing e-closures and DFA minimizations for probabilistic Finite Automata? Given that probabilistic NFAs might have multiple accepting paths for generating equivalent ...
- 5,521
4
votes
1
answer
673
views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
- 10.2k
2
votes
1
answer
160
views
NP-Completeness of Finding Minimum Automaton, in Gold's paper
I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "...
- 146
14
votes
1
answer
625
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 ...
- 5,759
9
votes
0
answers
105
views
Reference request: DFA linear-time minimization
What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time?
Here’s what I’ve been able to find so far:
The acyclic case has been solved. So any ...
- 414
8
votes
0
answers
148
views
Determining if transducer automaton has two states with intersecting images, without minimizing?
I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives ...
- 181
-1
votes
1
answer
73
views
How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it [closed]
I need to know for each of the $2^{2^3}$ boolean functions with $3$ inputs the
smallest boolean circuit made only of NAND gates computing it (smallest in terms
of the number gates).
I would be glad ...
- 1
4
votes
1
answer
266
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 ...
- 5,759
7
votes
1
answer
249
views
Finding a minimal DFA whose language has a desired intersection with another
Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$.
I would like to find another regular language $C$ such that $B = A \cap ...
0
votes
0
answers
34
views
Searchable finite field
Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$).
We say that $F$ is searchable if ...
- 471
1
vote
0
answers
147
views
QUBO formulation of a discrete-variable optimization problem
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
- 11.6k
5
votes
1
answer
237
views
Minimizing a submodular function given noisy oracle access
Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given noisy oracle access to $f$: on any $S$ and for any $\tau > 0$, one can ...
- 4,441
4
votes
0
answers
968
views
Minimizing a monotone submodular function under a cardinality constraint
I would like to know what the status of the following question is:
Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 \leq ...
- 14.2k
9
votes
2
answers
442
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 ...
- 6,947
1
vote
0
answers
127
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 ...
- 4,439
1
vote
0
answers
208
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 ...
1
vote
0
answers
561
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 ...
- 19
15
votes
2
answers
585
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 ...
- 16.4k
3
votes
0
answers
129
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 ...
CommunityBot
- 1
3
votes
0
answers
1k
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 ...
- 31
7
votes
2
answers
455
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 ...
CommunityBot
- 1
1
vote
0
answers
718
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 ...
- 1,573
1
vote
0
answers
40
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 ...
- 164
4
votes
3
answers
654
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 ...
- 3,160