Journal article

Publication year: 2023

Journal: Theoretical Computer Science

Volume number: 966

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2023.114001

Publisher: Elsevier

Abstract: 
Partial word finite automata are deterministic finite automata that may have state transitions on a special symbol  which represents an unknown symbol or a hole in the word. Together with a subset of the input alphabet that gives the symbols which may be substituted for the , a partial word finite automaton (-DFA) represents a regular language. However, this substitution implies a certain form of limited nondeterminism in the computations when the -transitions are replaced by ordinary transitions. In this paper we consider the state complexity of partial word finite automata accepting finite languages. We study the state complexity of the NFA to -DFA conversion for finite languages as well as the state complexity of the -DFA to DFA conversion for finite languages. Then we consider the operational state complexity with respect to complementation, union, reversal, and concatenation of finite languages. It turns out that the upper and lower bounds for all these operations are exponential. Moreover, we establish a state complexity hierarchy on the number of productive -transitions that may appear in -DFAs accepting finite languages. The levels of the hierarchy are separated by quadratic state costs.& COPY; 2023 Elsevier B.V. All rights reserved.

Harvard Citation style: Kutrib, M. and Wendlandt, M. (2023) State complexity of finite partial languages, Theoretical Computer Science, 966, Article 114001. https://doi.org/10.1016/j.tcs.2023.114001

APA Citation style: Kutrib, M., & Wendlandt, M. (2023). State complexity of finite partial languages. Theoretical Computer Science. 966, Article 114001. https://doi.org/10.1016/j.tcs.2023.114001