Skip to Main content Skip to Navigation
New interface
Conference papers

NFA-to-DFA Trade-Off for Regular Operations

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
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
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


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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


Files downloads