Journalartikel

Jahr der Veröffentlichung: 2020

Seiten: 1159-1177

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 31

Heftnummer: 8

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054120420083

Verlag: World Scientific Publishing

Abstract: 
We examine the accepting state complexity, i.e., the minimal number of accepting states of deterministic finite automata for languages resulting from unary and binary operations on languages with accepting state complexity given as a parameter. This is a continuation of the work of [J. Dassow: On the number of accepting states of finite automata, J. Autom., Lang. Comb., 21, 2016]. We solve most of the open problems mentioned thereof. In particular, we consider the operations of intersection, symmetric difference, right and left quotients, reversal, and permutation (on finite languages), where we obtain precise ranges of accepting state complexities. We also consider symmetric difference on unary finite languages where we obtain a non-contiguous range of accepting state complexities.

Harvard-Zitierstil: Hospodar, M. and Holzer, M. (2020) The Ranges of Accepting State Complexities of Languages Resulting from Some Operations, International Journal of Foundations of Computer Science, 31(8), pp. 1159-1177. https://doi.org/10.1142/S0129054120420083

APA-Zitierstil: Hospodar, M., & Holzer, M. (2020). The Ranges of Accepting State Complexities of Languages Resulting from Some Operations. International Journal of Foundations of Computer Science. 31(8), 1159-1177. https://doi.org/10.1142/S0129054120420083