Journalartikel

Jahr der Veröffentlichung: 2023

Zeitschrift: Theoretical Computer Science

Bandnummer: 966

ISSN: 0304-3975

eISSN: 1879-2294

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

Verlag: 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-Zitierstil: 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-Zitierstil: 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