Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina Jiraskova), but I can't understand what the practical implications of state complexity would be. The first trivial thought that struck me was that higher complexity would require more time and space by the machine. Is this correct? Also are there any other places where state complexity is relevant and signinficant?

Edit: The state complexity of a regular language is the smallest number of states in any deterministic finite automaton (dfa) accepting the language. The nondeterministic state complexity of a regular language is defined as the smallest number of states in any nondeterministic finite automaton (nfa) for the language.

share|improve this question
    
Sure thing. Edited the question! –  Airmine Nov 1 '12 at 15:56
    
It seems possible the paper you are reading answers the question to some degree...? Can you cite it in more detail eg the title & preferably a link to the pdf if available? FSM state complexity shows up in many applications & also has theoretical implications... –  vzn Nov 1 '12 at 18:15
    
Yes, I did look through the paper and looked through the references. Couldn't find much related to the applications of state complexity. –  Airmine Nov 1 '12 at 18:45
3  
just about any FSM application (which there are many) must consider state complexity for nontrivial, "big" problems. example. FSMs are used in speech recognition where the states are phonemes & this can lead to large FSMs. FSMs are also used extensively in EE applications eg circuits etc. there a FSM with high complexity is a "big" circuit. however the paper in question is mainly looking at the theoretical complexity of the problem where upper/lower bounds on "blowup" or "efficient minimization" (compression) are key properties to study.... –  vzn Nov 1 '12 at 21:14
    
Not exactly "practical", but state complexity plays a role in Diversity-based inference of finite automata by Rivest and Schapire: [conference; journal]. –  Neal Young Nov 4 '12 at 16:25

3 Answers 3

up vote 16 down vote accepted

State complexity is really about concise description of an object (in this case, a regular language), not about computational complexity. The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and Formal Systems" (see http://people.csail.mit.edu/meyer/economy-of-description.pdf ). This is still an active area, with a yearly conference (DCFS - Descriptional Complexity of Formal Systems).

As for applications, any place where your program essentially relies on a finite-state machine (e.g., parsers) it will be good to have this finite-state machine as small as possible.

share|improve this answer
1  
Oh, okay. So basically reducing the state complexity helps in achieving a minimal representation of a given language, rather than make it easier to process? –  Airmine Nov 27 '12 at 5:53

Let me add a concrete example to the excellent answer of Jeffrey Shallit.

Suppose you want to create a Scrabble (TM) dictionary. You can think of several ways to represent your dictionary, like list of words, tries (letter trees) or deterministic automata. According to [1], minimizing a trie to a dawg [= DFA] produces an amazing savings in space; the number of nodes is reduced from 117,150 to 19,853. The lexicon represented as a raw word list takes about 780 Kbytes, while our dawg can be represented in 175 Kbytes.

As you can see, the state complexity really matters in this case, especially if you want to write an efficient program as the authors did.

[1] Appel and Jacobson The World's Fastest Scrabble Program, Communications of the ACM 31, 572-578 (1988).

share|improve this answer

The proof that it is decidable whether an arbitrary deterministic context-free grammar (or equivalently a deterministic pushdown automaton) has an equivalent finite state automaton describing the same language is essentially a proof of the state complexity of finite automatons describing deterministic context-free languages: the bound on the size of these finite automatons in terms of the deterministic automatons gives bounds on the length of the decision procedure.

For details, see "Regularity and related problems for deterministic pushdown automata." by Leslie G. Valiant.

share|improve this answer
    
Interesting. Thank You! –  Airmine Nov 27 '12 at 17:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.