Please use this identifier to cite or link to this item:
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
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 SizeFormat 
107485.pdf545.9 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.