Journalartikel

Jahr der Veröffentlichung: 2023

Seiten: 987-1022

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 34

Heftnummer: 08

ISSN: 0129-0541

eISSN: 1793-6373

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

Verlag: World Scientific Publishing

Abstract: 
We investigate the state complexity of languages resulting from the cascade product of two minimal deterministic finite automata with n and m states, respectively. More precisely we study the magic number problem of the cascade product operation and show what range of complexities can be produced in case the left automaton is unary, that is, has only a singleton letter alphabet. Here we distinguish the cases when the involved automata are reset automata, permutation automata, permutation-reset automata, or do not have any restriction on their structure. It turns out that the picture on the obtained state complexities of the cascade product is diverse, and for all cases, except where the left automaton is a unary permutation(-reset) or a deterministic finite automaton without structural restrictions, and the right one is a reset automaton or a deterministic finite automaton without structural restrictions, we are able to identify state sizes that cannot be reached - these numbers are called "magic."

Harvard-Zitierstil: Holzer, M. and Rauch, C. (2023) The Range of State Complexities of Languages Resulting from the Cascade Product - The Unary Case, International Journal of Foundations of Computer Science, 34(08), pp. 987-1022. https://doi.org/10.1142/S0129054123430049

APA-Zitierstil: Holzer, M., & Rauch, C. (2023). The Range of State Complexities of Languages Resulting from the Cascade Product - The Unary Case. International Journal of Foundations of Computer Science. 34(08), 987-1022. https://doi.org/10.1142/S0129054123430049