Incomplete operational transition complexity of regular languages

• Tipo: Artigo em Revista Científica Internacional
• Data: 2015

Autores

Eva Maia (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogerio Reis (Autor) FCUP

Revista

Título: Information and Computation

Vol. 244

Páginas: 1-22

ISSN: 0890-5401

Editora: Elsevier

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 6 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 22