### Abstract

The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is mn - 1 for the unambiguous concatenation, it is known to be m2^{n-1} - 2^{n-2} (Daley et al. “Orthogonal concatenation: Language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3/8 2^{n}+1. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m + n-2, and unambiguous star requires n-2 states in the worst case.

Original language | English |
---|---|

Title of host publication | Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings |

Publisher | Springer |

Pages | 188-199 |

Number of pages | 12 |

ISBN (Print) | 9783319946306 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 - Halifax Duration: 25 Jul 2018 → 27 Jul 2018 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10952 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 |
---|---|

Country | Canada |

City | Halifax |

Period | 25/07/18 → 27/07/18 |

### Fingerprint

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings*(pp. 188-199). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10952 LNCS). Springer. https://doi.org/10.1007/978-3-319-94631-3_16