# P11314: Is the recursive optional-letter NFA construction always transition-minimal?

- ID: `P11314`
- Reference: `optional-letter-nfa-recursive-transition-optimality`
- Page: https://theoremdb.org/statements/P11314
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: b5a83bd9bdbf7dfdc7134c15b7360f889389e7bc
- Current Markdown: https://api.theoremdb.org/v1/statements/optional-letter-nfa-recursive-transition-optimality?representation=markdown
- Record maturity: Reviewed problem

## The problem

Let \(c_1\),...,c_n be distinct symbols and let L_n be the language of all subsequences of c_1...c_n, equivalently the language denoted by c_1?c_2?...c_n?. Let a(n) be the minimum number of labeled transitions in an epsilon-free NFA recognizing exactly L_n. The construction of el Abdalaoui, Dahmoune, and Ziadi recursively splits a minimum-cost leaf in its full-binary-tree encoding and converts the resulting partition system into such an NFA. Does that construction use exactly a(n) transitions for every n?

## Status

The reviewed record remains open.

## Research packet

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `optional-letter-nfa-recursive-transition-optimality`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.