New interface

Abstract : We examine the operational state complexity assuming that the operands of a regular operation are represented by nondeterministic finite automata, while the language resulting from the operation is required to be represented by a deterministic finite automaton. We get tight upper bounds $2^n$ for complementation, reversal, and star, $2^m$ for left and right quotient, $2^{m+n}$ for union and symmetric difference, $2^{m+n}-2^m-2^n+2$ for intersection, $2^{m+n}-2^n+1$ for difference, $\frac{3}{4}2^{m+n}$ for concatenation, and $2^{mn}$ for shuffle. We use a binary alphabet to describe witnesses for complementation, reversal, star, and left and right quotient, and a quaternary alphabet otherwise. Whenever we use a binary alphabet, it is always optimal.
Document type :
Conference papers
Domain :

Cited literature [15 references]

https://hal.inria.fr/hal-02387289
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, November 29, 2019 - 4:35:40 PM
Last modification on : Friday, November 29, 2019 - 5:01:53 PM

File

480958_1_En_14_Chapter.pdf
Files produced by the author(s)

Citation

Galina Jirásková, Ivana Krajňáková. NFA-to-DFA Trade-Off for Regular Operations. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.184-196, ⟨10.1007/978-3-030-23247-4_14⟩. ⟨hal-02387289⟩

Record views