Mergible states in large NFA



Title Mergible states in large NFA
Author(s) Cezar Campeanu, Nicolae Santean, Sheng Yu
Journal Theoretical Computer Science
Date 2005
Volume 330
Issue 1
Start page 23
End page 34
Abstract Quite often, trivial problems stated for deterministic finite automata (DFA) are surprisingly difficult for the non-deterministic case (NFA). In any non-minimal DFA for a given regular language, we can find two equivalent states which can be “merged” without changing the accepted language. This is not the case for NFA, where we can have non-minimal automata with no “mergible” states. In this paper, we prove a very basic result for NFA, that for a given regular language, any NFA of size greater than a computable constant must contain mergible states. Even more, we parameterized this constant in order to guarantee groups of an arbitrary number of mergible states.
DOI 10.1016/j.tcs.2004.09.008

Using APA 6th Edition citation style.

[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]

Times viewed: 426

Adding this citation to "My List" will allow you to export this citation in other styles.