%0 Conference Proceedings
%T NFA-to-DFA Trade-Off for Regular Operations
%+ Slovak Academy of Sciences (SAS)
%A Jirásková, Galina
%A Krajňáková, Ivana
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 184-196
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_14
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387289/document
%2 https://inria.hal.science/hal-02387289/file/480958_1_En_14_Chapter.pdf
%L hal-02387289
%U https://inria.hal.science/hal-02387289
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612