@mogoodrich You may be more familiar with them than you’re aware (know regex?).
I understand the OpenMRS usage of the terms “initial” and “terminal” has somewhat different meanings than I may use at times in the following explanation and could also add to some confusion if misunderstood to mean the patient would “immediately” be transitioned through the entire program workflow or, though it is another valid application of this type of model, allowing or rejecting enrollment to a program. I wouldn’t call myself an expert either, but from my study and use of these models, they seem like a reasonable starting point. I hope this thread can be useful in spurring discussion on this topic, and determining if any of it would be a helpful/needed addition to OpenMRS Patient Programs.
A Finite State Automaton (FSA) is a general category of these models, and you may see it mentioned more frequently. In Deterministic Finite Automata (DFA) the current state is known and repeatable given a sequence of inputs. The states and transitions can be viewed as a graph (in the CS ADT sense of the word), with each edge between vertices representing a particular valid transition (i.e. given some valid input “symbol”, that outgoing edge will be taken from the current vertex to the next vertex, or if there is no valid edge, reset to the initial state/output “invalid”/et c.). Here “Finite” refers to the set of vertices (that it is limited and known) and Deterministic in that the state (vertex) arrived at, given a particular input sequence, is always the same. In drawings of these graphs, the edges have the input “symbol” that selects that edge for traversal written over them. A Finite State Transducer (FST) produces output corresponding to the edge traversed (drawings usually show the input/output pair over the edge). A Non-deterministic Finite Automaton (NFA) allows two or more outgoing edges to correspond to a single input (not that they’re both traversed, but that either edge could be taken, hence the non-determinism).
For more complex conditions for edges (e.g. patient has treatment planned and a referred specialist for treatment and a treatment date scheduled), the complexity of the graph could be reduced using combinational logic to reduce those conditions to a single “symbol” designated for that edge/transition ( similarly to strongly connected component based complexity reduction in graphs, or select lines/output on a muxer ).
I’m not suggesting the strictest definition of any of these be adhered to (there’s a rigorous formal and mathematical language for all of these various things, but I won’t go into that).
Generally, in their most basic form, these systems are simply used to determine if a string or pattern is present or valid (DFA/FSA) (basically output a 0 or 1 after all is said and done, depending on if a “terminal” state was reached) (e.g. was there a regex match? is this a keyword of the language or a previously defined variable?). FSTs are used in translating from one “language” to another (FST, e.g. outputs: “walk -ed” => “verb past tense”, a programming language compiled to intermediate or machine code, simple physical machines: a player piano, a Jacquard loom). Both of these are frequently used in compilers and still in use in computational linguistics even today post neural nets.
In systems like Regular Expressions (e.g. a search pattern for grep), self referencing loop edges are possible (e.g. a*b), though I’m not suggesting there’s any use for that here (though it currently appears to be allowed in OpenMRS, see ProgramWorkflow().isLegalTransition() and PatientProgram.transitionToState()).
(I’ll try not to digress too much further, as I could go into more electrical engineering terminology to describe Finite State Machines (FSM), like Moore, Mealy and Turing machine definitions. Each of which with their own complexities, but can be used to describe functions (of various complexities) with varying conditions on what is considered when output is calculated, if there is “memory”, et c).
While there’s no specific need to “verify” a sequence of states at the moment (though that could be a nice benefit in more complicated systems), it is a more rigorous model than the current implementation (even if the conversation just leads to designing workflows using formal state transition diagrams). If it’s easier to talk about it as just a specialized graph model in this context, that’s fine by me.
Currently in OpenMRS, the actual initial state (when the patient is in a program but no program workflow state has been entered) is followed by those states marked as “initial”, where they are the only valid transitions from the actual initial state. Then any transition to any state within that program workflow is “valid” until a “terminal” state has been selected, at which point the enrollment in the program ends. Since there’s limited restrictions on which states are valid when, it is very loosely defined, which some developers might see as beneficial. However, while it is somewhat flexible, it does allow some unintended transitions, and prevents some valid transitions e.g. in @dkayiwa 's previously
linked diagram
The diagram in question (note that it is not a formal “state transition diagram”), using the current OpenMRS patient program workflow state logic, it is possible to go from second trimester back to first or from first directly to third. It also omits a few terribly unfortunate alternative “terminal” states like false pregnancy, miscarriage, and premature birth, and misses other “initial state” possibilities of someone entering care when they’re already in second or third trimester.
Another example might be a cancer treatment program. This is just an example, I don’t want to make it too complicated by breaking it out into multiple workflows, but that might be more accurate in through a providers’ eyes.
A patient might have some symptom of a cancer (or it could be specifically identified though some regular test), at which point they enter the program and undergo further tests, eventually to determine if it is malignant or benign, they then enter a state where the cells were benign, but still need regular checkups to monitor for malignancy. At some point, malignant cells may be found, and they enter a treatment state. After treatment, the cancer goes into remission and they return to a regular checkup schedule state to monitor for recurrence. The patient could also be moving to a new location, simply lost to followup, or changing healthcare systems and need continuance of care. This implies the need to have some states for leaving the program at any time (freely moving to a “terminal” state) or alternatively unique, intake “initial” state(s) before moving to specific main workflow state(s).
The design choices like whether the initial monitoring state and recurrence monitoring state differ, are still in the hands of the designers/implementers, but I think it’s important that those sorts of questions be considered more thoroughly, and that the underlying workflow design accounts for the designs that are in use, while allowing the for improvements in the Knowledge Organization and Navigation options of OpenMRS. With many reports, forms, and other pieces of related information stored in an OpenMRS deployment, providing directed and automated access to those forms and representations of information based on workflow state(s) seems like a useful improvement, even one that OWAs using REST endpoints could benefit from having.
@mogoodrich I know we’ve also had a brief conversation about how the patient program workflow state history is (and in some ways is not) stored in the database. The relational model doesn’t really lend itself to ordering by the previous state for instance (if it were to be stored with the current state). There is additionally the question of whether storing the input that leads to the transition is another useful piece of information that could/should be preserved.
I’m just putting this out there for discussion. For the current use case I’ve been implementing, I have been able to do what’s required by implementing the additional logic myself, but in general, if this is a common need, it might make sense to provide it in core or at least a specialized module.
could you give a quick summary of (or provide a link to) what DFA/FSA/FST means?