Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Cezar Campeanu, Nicolae Santean, and Sheng Yu. Mergible states in large NFA. Theoretical Computer Science, 330 Issue 1, pp. 23-34, 2005.

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.

Keywords: Nondeterministic finite automata; Mergible states; Number of states; Equivalent states

URL: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4DFSWBM-7&_user=1069243&_coverDate=01%2F31%2F2005&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000051268&_version=1&_urlVersion=0&_userid=1069243&md5=19dccddea88f3acfbbe9e4e7955cfaa4

Posted by Cezar Campeanu

Back

   
© Ad Astra 2001-2013