wchargin

Hmm… consider the following. Your FSM is acyclic iff you can assign each state an integer depth such that a state at depth d only ever transitions to states at depths strictly greater than d. So consider the following tables:

    CREATE TABLE states (
        state order_state PRIMARY KEY,
        depth int NOT NULL,
        UNIQUE(state, depth)
    );
    CREATE TABLE transitions (
        start_state order_state NOT NULL,
        event order_event NOT NULL,
        end_state order_state NOT NULL,
        start_depth int NOT NULL,
        end_depth int NOT NULL,
        CONSTRAINT transitions_start_depth_correct
            FOREIGN KEY(start_state, start_depth) REFERENCES states(state, depth)
            ON UPDATE CASCADE,
        CONSTRAINT transitions_end_depth_correct
            FOREIGN KEY(end_state, end_depth) REFERENCES states(state, depth)
            ON UPDATE CASCADE,
        CONSTRAINT transitions_depth_increases CHECK(end_depth > start_depth),
        PRIMARY KEY(start_state, event)
    );

Let's bang on it for a quick test. You can define a state machine; here's one that roughly matches the regex `^(AB|BA)$` (I know I'm being a bit sloppy):

    fsm=> CREATE DOMAIN order_state AS text;
    CREATE DOMAIN
    fsm=> CREATE DOMAIN order_event AS text;
    CREATE DOMAIN
    fsm=> -- "CREATE TABLE"s as above, then:
    fsm=> INSERT INTO states(state, depth) VALUES('start', 1), ('a', 2), ('b', 2), ('done', 3), ('error', 3);
    INSERT 0 5
    fsm=> INSERT INTO transitions(start_state, event, end_state, start_depth, end_depth) VALUES('start', 'A', 'a', 1, 2), ('start', 'B', 'b', 1, 2), ('a', 'B', 'done', 2, 3), ('b', 'A', 'done', 2, 3), ('a', 'A', 'error', 2, 3), ('b', 'B', 'error', 2, 3);
    INSERT 0 6

And, as you need to modify it, you can increase a node's depth to make room for intervening nodes:

    fsm=> UPDATE states SET depth = 4 WHERE state = 'error';
    UPDATE 1
    fsm=> TABLE transitions;
     start_state | event | end_state | start_depth | end_depth 
    -------------+-------+-----------+-------------+-----------
     start       | A     | a         |           1 |         2
     start       | B     | b         |           1 |         2
     a           | B     | done      |           2 |         3
     b           | A     | done      |           2 |         3
     a           | A     | error     |           2 |         4
     b           | B     | error     |           2 |         4
    (6 rows)

But you can't decrease a node's depth too far:

    fsm=> UPDATE states SET depth = 2 WHERE state = 'error';
    ERROR:  new row for relation "transitions" violates check constraint "transitions_depth_increases"
    DETAIL:  Failing row contains (a, A, error, 2, 2).
    CONTEXT:  SQL statement "UPDATE ONLY "public"."transitions" SET "end_state" = $1, "end_depth" = $2 WHERE $3::pg_catalog.text OPERATOR(pg_catalog.=) "end_state"::pg_catalog.text AND $4 OPERATOR(pg_catalog.=) "end_depth""

And you can't introduce transitions that don't increase depth:

    fsm=> INSERT INTO transitions(start_state, event, end_state, start_depth, end_depth) VALUES('done', 'AGAIN!', 'start', 3, 1);
    ERROR:  new row for relation "transitions" violates check constraint "transitions_depth_increases"
    DETAIL:  Failing row contains (done, AGAIN!, start, 3, 1).

Now, I don't know that I would immediately recommend this for high-throughput production use. You're storing "unnecessary" state not once but many times (each state's depth appears `1 + \deg(v)` times), plus additional indices and lookups. But I do think it meets the desired consistency goals!