Incomplete operational transition complexity of regular languages

• Type: Article in International Scientific Journal
• Date: 2015

Authors

Eva Maia (Author) Other; Nelma Moreira (Author) FCUP; Rogerio Reis (Author) FCUP

Journal

Title: Information and Computation

Vol. 244

Pages: 1-22

ISSN: 0890-5401

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 6 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-00G-JJE

DOI: 10.1016/j.ic.2015.08.004

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 22