First of all, that sounded negative and I'm totally not knocking Xstate. I'm pro any library that encourages people to think about state machines :D

I'm really speaking tactically about how best to represent the machine, more of an optimization thing. For that, the features that you mentioned do help, no question there. Statecharts is a great formalism overall. But in my opinion, they help more at the macro level, like when thinking about the entire UI as a single state machine and how to modularize that.

Hierarchy and orthogonality are not always present - sometimes state variables truly interact. I'm speaking more about that scenario. I'll take an example right from the Xstate documentation:

  list: {
    initial: 'none',
    states: {
      none: {
        on: { BULLETS: 'bullets', NUMBERS: 'numbers' }
      },
      bullets: {
        on: { NONE: 'none', NUMBERS: 'numbers' }
      },
      numbers: {
        on: { BULLETS: 'bullets', NONE: 'none' }
      }
    }
  }

Here, we have a state machine that looks like it powers some logic in a word processor, where a user can create lists. You can toggle bulleted or numbered lists on and off, as well as switch between them once either has been selected. Since each state can transition to each other state, each state references each other state in the transition description. What happens when you add another state there, let's say we can have a list with letters as indexes. You'd have to add another transition from each existing state to the new one, and add a transition from the new state to all the other ones. This is an O(N) operation as we agreed since every new state means there are N possible edges from it to all other states, and each existing state can have an edge to the new state. I believe this is what people mean when state machines are "hard to modify."

What if instead we used variables to represent the state, and had a single function which determined the next state to go to based on the existing state:

  type State = {
    showingBullets: Boolean,
    showingNumbers: Boolean,
  } 

  enum Action {
    ToggleBullets,
    ToggleNumbers,
  }

  function next(state: State, action: Action): State {
    let nextState = { showingBullets: false, showingNumbers: false };

    switch (action) {
    case Action.ToggleBullets:
      nextState.showingBullets = !state.showingBullets;
      break;
    case Action.ToggleNumbers:
      nextState.showingNumbers = !state.showingNumbers;
      break;
    };

    return nextState;
  }

Now, the process of adding a new state would be just adding a new case in the switch statement. That's constant time, O(1). This is because the next function is actually a relation - it can map a single state to multiple next states.

I will admit, this may be personal preference. With the Xstate approach, where you specify all transitions explicitly, there's no thinking. You just read which state maps to which next state. A relation has logic, which means you have to compute in your head all of the possible next states. It's the tradeoff between expressive power and explicitness.

So allocate an instance from an implied set of states instead of explicitly traversing the enumeration. Nice for a business process likely to need change, or where the actual state space is large, but inappropriate for something like utf8 decode where fixed space is required.

I'm not familiar with utf8 decoding, and I focus all of my efforts on thinking about business software. I think it's pretty guaranteed that different representations of anything will make sense for different use cases.

It’s funny, I look at this and think “redux”.

Redux absolutely implements a state machine. The next state is a function of the current state and an input action. That’s the textbook definition of a state machine.

Thank you very much for this detailed explanation, I really appreciate it!