14
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Sure thing. Edited the question! $\endgroup$
    – Airmine
    Nov 1, 2012 at 15:56
  • $\begingroup$ 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... $\endgroup$
    – vzn
    Nov 1, 2012 at 18:15
  • $\begingroup$ Yes, I did look through the paper and looked through the references. Couldn't find much related to the applications of state complexity. $\endgroup$
    – Airmine
    Nov 1, 2012 at 18:45
  • 3
    $\begingroup$ 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.... $\endgroup$
    – vzn
    Nov 1, 2012 at 21:14
  • $\begingroup$ Not exactly "practical", but state complexity plays a role in Diversity-based inference of finite automata by Rivest and Schapire: [conference; journal]. $\endgroup$
    – Neal Young
    Nov 4, 2012 at 16:25

3 Answers 3

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Airmine
    Nov 27, 2012 at 5:53
  • 1
    $\begingroup$ Also, since most algorithms on automata directly depend on state complexity, minimizing states is often done with an ulterior motive of minimizing computational complexity. $\endgroup$
    – Denis
    Oct 9, 2019 at 9:06
9
$\begingroup$

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).

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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