Please use this identifier to cite or link to this item:
https://hdl.handle.net/10216/90779
Author(s): | Eva Maia Nelma Moreira Rogerio Reis |
Title: | Incomplete operational transition complexity of regular languages |
Issue Date: | 2015 |
Abstract: | The state complexity of basic operations on regular languages considering complete deterministic finite automata (DFA) has been extensively studied in the literature. But, if incomplete DFAs are considered, transition complexity is also a significant measure. In this paper we study the incomplete (deterministic) state and transition complexity of some operations for regular and finite languages. For regular languages we give a new tight upper bound for the transition complexity of the union, which refutes the conjecture presented by Y. Gao et al. For finite languages, we correct the published state complexity of concatenation for complete DFAs and provide a tight upper bound for the case when the right operand is larger than the left one. We also present some experimental results to test the behavior of those operations on the average case, and we conjecture that for many operations and in practical applications the worst-case complexity is seldom reached. |
Subject: | Ciências da computação e da informação Computer and information sciences |
Scientific areas: | Ciências exactas e naturais::Ciências da computação e da informação Natural sciences::Computer and information sciences |
URI: | https://repositorio-aberto.up.pt/handle/10216/90779 |
Document Type: | Artigo em Revista Científica Internacional |
Rights: | openAccess |
Appears in Collections: | FCUP - Artigo em Revista Científica Internacional |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
107485.pdf | 545.9 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.