5
$\begingroup$

I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each Turing machine as one of the criteria to guide the evolution process.

However, I couldn't find any references as to a canonical complexity metric for FSMs. I imagine the metric would include some combination of the number of states, number of transitions, and number of input symbols, but I'm not sure how these would be combined appropriately into a normalized metric.

Is there a canonical (ideally normalized) complexity metric for finite state machines?

$\endgroup$
6
  • 1
    $\begingroup$ The canonical measure is the number of states. The alphabet is usually fixed, and we don't care about the number of transitions. $\endgroup$ Commented Mar 1, 2016 at 23:14
  • 1
    $\begingroup$ Why don't we care about the number of transitions? E.g. if we look at complexity in terms of the amount of information required to represent the transition table, then surely the number of transitions is important? $\endgroup$ Commented Mar 1, 2016 at 23:16
  • 1
    $\begingroup$ We just don't. That's the canonical measure. $\endgroup$ Commented Mar 1, 2016 at 23:17
  • 1
    $\begingroup$ So, at the limits, an FSM with N states and no transitions is equally complex to a fully connected FSM with the same N states? $\endgroup$ Commented Mar 1, 2016 at 23:21
  • 1
    $\begingroup$ Most of the papers I've seen restrict the automata to be trim, which means that all the states are accessible and co-accessible. Accessible means that each state in the automaton is reachable from the start state via some path. Co-accessible means that there's a path from each state to some final state. This paper discusses these terms. I've also seen the requirement that the transition function be total and that there be a single sink state. But yes, the usual measure is just to count states. $\endgroup$
    – ShyPerson
    Commented May 22, 2021 at 4:04

4 Answers 4

9
$\begingroup$

Yes, there is a canonical complexity metric for finite state machines: the number of states. It's as simple as that.

The number of transitions or input symbols don't matter (for this standard, canonical metric). We don't use a normalized metric based on the combination of such values. We just count the number of states.

$\endgroup$
4
  • 1
    $\begingroup$ A case in point is NFA minimization, where we want to minimize the number of states. See for example hermann-gruber.com/data/lata07-final.pdf. $\endgroup$ Commented Mar 2, 2016 at 8:28
  • 1
    $\begingroup$ @YuvalFilmus Gruber in fact does care about counting transitions in some of his papers. Citation needed for the claim that we only care about states. $\endgroup$ Commented May 22, 2021 at 2:19
  • $\begingroup$ If anything, counting the number of transitions only makes sense for nondeterministic automata. A deterministic finite automaton with $n$ states has exactly $n|\Sigma|$ transitions, so this is a redundant measure. $\endgroup$ Commented May 25, 2021 at 19:10
  • $\begingroup$ @BjørnKjos-Hanssen, Sure. There all sorts of things we might care about, depending on the situation. Agreed. I never claimed "we only care about states". That's not what my answer wrote, and that's not what Yuval Filmus wrote, either. So I don't think there's any need to provide a citation for a claim that hasn't been made. What I wrote is that the number of states is the canonical complexity measure. By that I mean it is the usual measure, the most common measure, the most typical. Of course there may be situations where we care about other things. $\endgroup$
    – D.W.
    Commented May 25, 2021 at 20:10
4
$\begingroup$

If you set aside the mathematical definition of complexity for FSMs (in @D.W.'s correct answer), from a systems engineering perspective, there is no agreed-upon algorithm or formula for measuring the complexity of any process. However there are a lot of good ideas for measuring complexity of computer programs in the references below. Look for mention of "McCabe cycolomatic complexity", "number of states/nodes", "number of transitions/edges", etc:

The last reference to "Halstead Complexity Measures" gives formulas for practical measures like volume, difficulty, and effort for any computer program (including FSMs). Halstead even proposed formulas to estimate the likely number of "Bugs Delivered."

$\endgroup$
2
$\begingroup$

In case your finite state machines are "programs" of some sort, and you want to obtain the simplest program, it may make sense to use the length of the program corresponding to the FSM as your complexity metric, for some hypothetical mapping of FSMs to programs: e.g., $$\text{numTransitions} \cdot (\log(\text{alphabetSize}) + \log(\text{numStates}))$$ could be reasonable, as each transition requires $O(\log(\text{alphabetSize}) + \log(\text{numStates}))$ bits to encode.

$\endgroup$
-1
$\begingroup$

You could take the three-dimensional vector (states, transitions, symbols) as your measure of complexity.

  • Disadvantage: you get incomparable levels of complexity.

  • Advantage: you retain all the information.

$\endgroup$
3
  • $\begingroup$ In TCS we are often interested in complexity measures ranging over total orders, preferably the positive reals. $\endgroup$ Commented May 26, 2021 at 5:35
  • $\begingroup$ @YuvalFilmus sure, although for each "this is how we do it" there is a corresponding "why not try a different way" $\endgroup$ Commented May 26, 2021 at 5:46
  • 1
    $\begingroup$ Since otherwise it is difficult to talk about approximation algorithms, though bicriteria approximation is certainly a thing. $\endgroup$ Commented May 26, 2021 at 6:31

Your Answer

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

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