Models with propositionally labeled states can be described in terms of Kripke structures. More formally, a Kripke structure is a quadruple , where S is a set of states, R is the transition relation between states using one of the enabled operators, I is the set of initial states, and is a state labeling function. This formulation is close to the definition of a state space problem in Chapter 1 up to the absence of terminal states. That I may contain more than one start state helps to model some uncertainty in the system. In fact, by considering the set of possible states as one belief state set, this form of uncertainty can be compiled away.

For model checking, the desired property of the system is to be specified in some form of temporal logic. We already introduced linear temporal logic (LTL) in Chapter 13. Given a Kripke structure and a temporal formula f, the model checking problem is to find the set of states in M that satisfy f, and check whether the set of initial states belongs to this state set. We shortly write in this case.

The model checking problem is solved by searching the state space of the system. Ideally, the verification is completely automatic. The main challenge is the state explosion problem. The problem occurs in systems with many components that can interact with each other, so that the number of global states can be enormous. We observe that any propositional planning problem can be modeled as an LTL model checking problem as any propositional goal g can be expressed in the form of a counterexample to the temporal formula in LTL. If the problem is solvable, the LTL model checker will return a counterexample, which manifests a solution for the planning problem.

The inverse is also often true. Several model checking problems can be modeled as state space problems. In fact, the class of model checking problems that fit into the representation of a state space problem with a simple predicate should be evaluated at each individual state. Such problems are called safety properties. The intuition behind such a property is to say that something bad should not happen. In contrast, liveness properties refer to infinite runs with (lasso-shaped) counterexamples. The intuition is to say that something good will eventually occur.

In automata-based model checking the model and the specification are both transformed into automata for accepting infinite words. Such automata look like ordinary automata but accept if during the simulation of an infinite word one accepting state is visited infinitely often. This assumes that a system can be modeled by an automaton, which is possible when casting all states in the underlying Kripke structure for the model as being accepting. Any LTL formula can be transformed into an automata over infinite words even if this construction may be exponential in the size of the formula. Checking correctness is reduced to checking language emptiness. More formally, the model checking procedure validates that a model represented by an automaton M satisfies its specification represented by an automaton . The task is to verify if the language induced by the model is included in the language induced by the specification, for short. We have if and only if . In practice, checking language emptiness is more efficient than checking language inclusion. Moreover, we often construct the property automaton N for negation of the LTL formula, avoiding the posterior complementation of the automaton over infinite words. The property automaton is nondeterministic, such that both the model and the formula introduce branching to the search process.

Heuristics are evaluation functions that order the set of states to be explored, such that the states that are closer to the goal are considered first. Most search heuristics are state-to-goal distance estimates that are based on solving simplifications or abstractions of the overall search problems. Such heuristics are computed either offline, prior to the search in the concrete state space, or online for each encountered state (set). In a more general setting, heuristics are evaluation functions on generating paths rather than on states only.

The design of bug hunting estimates heavily depends on the type of error that is searched for. Example error classes for safety properties are system deadlocks, assertion or invariance violations. To guide the search, the error description is analyzed and evaluated for each state. In trail-directed search we search for a short counterexample for a particular error state that has been generated, for example, by simulating the system.

Abstractions often refer to relaxations of the model. If the abstraction is an overapproximation (each behavior in the abstract space has a corresponding one in the concrete space, which we will assume here), then a correctness proof for the specification in the abstract space implies the correctness in the concrete space.

Abstraction and heuristics are two sides of the same medal. Heuristics correspond to exact distances in some abstract search space. This leads to the general approach of abstraction-directed model checking (see Fig. 16.1). The model under verification is abstracted into some abstract model checking problem. If the property holds, then the model checker returns true. If not, in a directed model checking attempt the same abstraction can be used to guide the search in the concrete state space to falsify the property. If the property does not hold, a counterexample can be returned, and if it does hold, the property has been verified.

This framework does not include recursion as in counterexample-guided error refinement, a process illustrated in Figure 16.2. If the abstraction (heuristic) turns out to be too coarse, it is possible to iterate the process with a better one.

System invariants are Boolean predicates that hold in every global system state u. When searching for invariant violations it is helpful to estimate the number of system transitions until a state is reached where the invariant is violated. For a given formula f, let be an estimate of the number of transitions required until a state v is reached where f holds, starting from state u. Similarly, let denote the heuristic for the number of transitions necessary until f is violated.

In Figure 16.3, we illustrate a recursive definition of as a function of f. In the definition of for the use of addition suggests that and are independent, which may not be true. Consequently, the estimate is not a lower bound, affecting the optimality of algorithms like A*. If the aim is to obtain short but not necessarily optimal paths, we may tolerate inadmissibilities; otherwise, we may replace addition by maximization.

Formulas describing system invariants may contain other terms, such as relational operators and Boolean functions over queues. We extend the definition of and as shown in Figure 16.4.

Note that the estimate is coarse but nevertheless very effective in practice. It is possible to refine these definitions for specific cases. For instance, can be defined as in case and a is only ever decremented and b is only ever incremented.

The control state predicate definition is given in Figure 16.5. The distance matrix can be computed with the All Pairs Shortest Paths algorithm of Floyd and Warshall in cubic time (see Ch. 2).

The statement assert extends the model with logical assertions. Given that an assertion a labels a transition , with , then we say a is violated if the formula is satisfied.

In concurrent systems, a deadlock occurs if at least a subset of processes and resources is in a cyclic wait situation. State u is a deadlock if there is no outgoing transition from u to a successor state v and at least one end state of a process of the system is not valid. A local control state can be labeled as end to indicate that it is valid; that is, that the system may terminate if the process is in that state.

Some statements are always executable; among others, assignments, else statements, and run statements used to start processes. Other statements, such as send or receive operations or statements that involve the evaluation of a guard, depend on the current state of the system. For example, a send operation q!m is only executable if the queue q is not full, indicated by the predicate . Asynchronous untagged receive operations (q?x, with x variable) are not executable if the queue is empty; the corresponding formula is ¬empty . Asynchronous tagged receive operations (q?t, with t tag) are not executable if the head of the queue is a message tagged with a tag different from t; yielding the formula . Moreover, conditions are not executable if the value of the condition corresponding to the term c is false.

The Boolean function executable, ranging over tuples of statements and global system states, is summarized for asynchronous operations and Boolean conditions in Figure 16.6.

To estimate the smallest number of transitions from the current state to a deadlock state, we observe that in a deadlock state all processes are necessarily blocked. Hence, the active process heuristics use the number of active or nonblocked processes in a given state:where is defined asAssuming that the range of is contained in , the active processes heuristic is not very informative for protocols involving a small number of processes.

Deadlocks are global system states in which no progress is possible. Obviously, in a deadlock state each process is blocked in a local state that does not possess an enabled transition. It is not trivial to define a logical predicate that characterizes a state as a deadlock state that could at the same time be used as an input to the estimation function . We first explain what it means for a process to be blocked in its local state . This can be expressed by the predicate blocked_i, which states that the program counter of process must be equal to and that no outgoing transition t from state is executable:Suppose we are able to identify those local states in which a process i can block; that is, in which it can perform a potentially blocking operation. Let be the set of potentially blocking states within process i. A process is blocked if its control resides in some of the local states contained in . Hence, we define a predicate for determining whether a process is blocked in a global state u as the disjunction of for every local state c contained in :Deadlocks, however, are global states in which every process is blocked. Hence, the disjunction of for every process yields a formula that establishes whether a global state u is a deadlock state or not:Now we address the problem of identifying those local states in which a process can block. We call these states dangerous. A local state is dangerous if every outgoing local transition can block. Note that some transitions are always executable, for example, those corresponding to assignments. To the contrary, conditional statements and communication operations are not always executable. Consequently, a local state that has only potentially nonexecutable transitions should be classified as dangerous. Additionally, we may allow the protocol designer to identify states as dangerous. Chaining backward from these states, local distances to critical program counterlocations can be computed in linear time.

The deadlock characterization formula deadlock is constructed before the verification starts and is used during the search by applying the estimate , with f being a deadlock. Due to the first conjunction of the formula, estimating the distance to a deadlock state is done by summing the estimated distances for blocking each process separately. This assumes that the behavior of processes is entirely independent and obviously leads to a nonoptimistic estimate. We estimate the number of transitions required for blocking a process by taking the minimum estimated distance for a process to reach a local dangerous state and negate the enabledness of each outgoing transition in that state. This could lead again to a nonadmissible estimate, since we are assuming that the transitions performed to reach the dangerous state have no effect on disabling the outgoing transitions of that state.

It should be noted that deadlock characterizes many deadlock states that are never reached by the system. Consider two processes having local dangerous states , respectively. Assume that u has an outgoing transition for which the enabledness condition is the negation of the enabledness condition for the outgoing transition from v. In this particular case it is impossible to have a deadlock in which is blocked in local state u and is blocked in local state v, since either one of the two transitions must be executable. As a consequence the estimate could prefer states unlikely to lead to deadlocks. Another concern is the size of the resulting formula.

We describe now two heuristics that exploit the information of an already established error state. The first heuristic is designed to focus at exactly the state that was found in the error trail, while the second heuristic focuses on equivalent error states.

The liveness as safety model checking approach proposes to convert a liveness model checking problem into a safety model checking problem by roughly doubling the state vector size. The most important observation is that the exploration algorithms do not have to be rewritten.

In the lifted search space we search for shortest lasso-shaped counterexamples, without knowing the start of the cycle beforehand. We use the consistent heuristicof distances in N for finding accepting states in the original search space.

States in the lifted search space are abbreviated by tuples , with u recording the start state of the cycle, and v being the current search state. If we reach an accepting state, we immediately switch to a secondary search. Therefore, we observe two distinct cases: primary search, for which the accepting state has not yet reached; and cycle detection search, for which an accepting state has to be revisited. The state reached in secondary search is the goal. Because it is a successor of a secondary state, we can distinguish the situation from reaching such a state for the first time.

For all extended states in the lifted search space, let and . Now we are ready to merge the heuristics to one estimate:As each counterexample has to contain at least one accepting state in N, for primary states x we have that is a lower bound. For secondary states x, we havea lower bound to close the cycle and the lasso in total. Therefore, h is admissible. Moreover, we can strengthen the result.

It is not difficult to see that h is consistent; that is, for all successor states of x. As both and are monotone, only one of them is true at a time. Hence, we have to show that h is monotone in case of reaching an accepting state. Here we have that a predecessor x with an evaluation of spawns successors with evaluation values of . However, this incurs no problem as preserves monotonicity.

The model checking algorithm for directed external LTL search is an extension of external A* (see Ch. 8), which traverses the bucket file list along growing diagonals. On disk we store (packed) state pairs. Figure 16.7 illustrates a prototypical execution.

To encode communication protocols in PDDL, each process is represented by a finite-state automaton. Since is not difficult to come up with a specialized description, we are interested in a generic translation routine; the propositional encoding should reflect the graph structures of the processes and the communication queues.

In the example problem for converting the Dining Philosophers problem (see Ch. 10) the initial state is shown in Figure 16.8.

The encoding of the communication structure is based on representing updates in the channel as changes in an associated graph. The message-passing communication model realizes the ring-based implementation of the queue data structure. A queue is either empty (or full) if both pointers refer to the same queue state. A queue may consist of only one queue state, so the successor bucket of queue state 0 is the queue state 0 itself. In this case the grounded propositional encoding includes actions where the add and the delete lists share an atom. Here we make the standard assumption that deletion is done first. In Figure 16.8 (bottom) the propositions for one queue and the connection of two queues to one process are shown.

Globally shared and local variables are modeled using numerical variables. The only difference of local variables compared to shared ones is their restricted visibility scope, so that local variables are simply prefixed with the process in which they appear. If the protocol relies on pure message passing, no numerical state variable is needed, yielding a pure propositional model for the Dining Philosophers problem.

The PDDL domain encoding uses seven actions, named activate-trans, queue-read, queue-write,advance-queue-head, advance-empty-queue-tail, advance-nonempty-queue-tail, and process-trans. We show the activation of a process in Figure 16.9.

Briefly, the actions encode the protocol semantics as follows. Action activate-trans activates a transition in a process of a given type from local state to . Moreover, the action sets the predicate activate. This Boolean flag is a precondition of the queue-read and queue-write actions, which set propositions that initialize the reading/writing of a message. For queue Q in an activated transition querying message m, this corresponds to the expression Q?m, respectively Q!m. After the read/write operation has been initialized, the queue update actions:advance-queue-head, advance-empty-queue-tail, or advance-nonempty-queue-tail have to be applied. The actions respectively update the head and the tail positions, as needed to implement the requested read/write operation. The actions also set a settled flag, which is a precondition of every queue access action. Action process-trans can then be invoked. It executes the transition from local state to ; that is, sets the new local process state and resets the flags.

If the read message does not match the requested message, or the queue capacity is either too small or too large, then the active local state transition will block. If all active transitions in a process block, the process itself will block. If all processes are blocked, we have a deadlock in the system. Detection of such deadlocks can be implemented, either as a collection of specifically engineered actions or, more elegantly, as a set of derived predicates. In both cases we can infer, along the lines of argumentation outlined earlier, that a process/the entire system is blocked. The goal condition that makes the planners detect the deadlocks in the protocols is simply a conjunction of atoms requiring that all processes are blocked. The PDDL description for the derivation of a deadlock based on blocked read accesses is shown in Figure 16.10.

Extensions to feature LTL properties with PDDL are available via state trajectory constraints or temporally extended goals.

Timed automata can be viewed as an extension of classic finite automata with clocks and constraints defined on these clocks. These constraints, when corresponding to states, are called invariants, and restrict the time allowed to stay at the state. When connected to transitions these constraints are called guards. They restrict the use of the transitions. The clocks C are real-valued variables and measure durations. The values of all the clocks in the system are denoted as a vector, also called clock valuation function, . The constraints are defined over clocks and can be generated by the following grammar: For , a constraint is defined aswhere and . These constraints yield two different kinds of transitions. The first one (delay transition) is to wait for some duration in the current state s, provided the invariant holds. This lets only the clock variables increase. The other operation (edge transition) resets some clock variables while taking the transition t. The operation is possible given that the guard holds. We allow an edge transition to be taken without an increase in time.

Trajectories are alternating sequences of states and transitions and define a path within the automata. The reachability task is to determine if the goal in the form of partial assignment to the ordinary and clock variables can be reached or not. The optimal reachability problem is to find a trajectory that minimizes the overall path length.

For a reachability analysis on timed automata, we face the problem of an infinite-state space. This infiniteness is due to the fact that the clocks are real-valued and, hence, an exhaustive state space exploration suffers from infinite branching. This problem was solved with the introduction of a partitioning scheme based on regions. A region automata creates finitely many partitions of the infinite-state space based on the equivalent classes of the clock valuations. In model checking tools, though, a coarser representation called a zone is used. Formally, a zone Z over a set of clocks C is a finite conjunction of difference constraints of the form or , with and integer d. ¹

The semantics for delay and edge transitions in a timed automata are based on some basic operations. We restrict to changes in clock variables. For a clock vector u and a zone Z we write if u satisfies the constraints in Z. The two main operations on (clock) zones are: clock reset that resets all the clocks x, and delay (d time units) . The reachability problem in timed automata can then be reduced to the reachability analysis in zone automata. In a zone automata, each state is basically a symbolic state corresponding to one or many states in the original timed automata. The new state is represented as a tuple , with l being the discrete part containing the local state of the automata, and Z is the convex -dimensional hypersurface in Euclidean space. Semantically, now represents the set of all states with . Let denote the set of constraints defined on clocks C and let denote the power set of C. Formally, a timed automata is a tuple , where S is the set of states, is the initial state with an empty zone, is the transition relation making states to their successors, given the constraints on the edge are satisfied, assigns invariants to the states, and T is the set of final states.

Linearly priced timed automata are timed automata with (linear) cost variables. For the sake of brevity, we restrict their introduction to one cost variable c. Cost increases at states with respect to a predefined rate and in transitions with respect to an update operation. The cost-optimal reachability problem is to find a trajectory that minimizes the overall path costs. Figure 16.16 shows a timed automata. The minimum cost of reaching location with cost 13 corresponds to the trajectory of waiting 0 steps in and then taking the transition to , where four time steps are spent until the transition to the goal in .

Similar to timed automata, for priced timed automata we use the notion of priced zones to represent the symbolic states. Let be the unique clock valuation of Z such that for all and , we have ; that is, it represents the lowest corner of the -dimensional hyper-surface representing a zone. In the following, is referred to as the zone offset. For the internal state representation, we exploit the fact that prices are linear cost hyperplanes of zones. A priced zone is a triple , where Z is a zone, integer c describes the cost of , and gives the rate for a given clock. In other words, prices of zones are defined by the respective slopes that the cost function hyperplane has in the direction of the clock variable axes. Furthermore, with , we denote the cost evaluation function based on priced zones . The cost value f for a given clock in the priced zone can then be computed as . Formally, a linearly priced timed automata over clocks C is a tuple , where S is a finite set of locations; is the initial state with empty priced zone ; is the set of transitions, each consisting of a parent state, the guard on the transition, the clocks to reset, and the successor state; assigns invariants to locations; and assigns prices to the states and transitions.

In priced real-time systems, the costs f denote a monotonic increasing function implying that for all we have . It is clear that breadth-first search does not guarantee a cost-optimal solution. A natural extension is to continue the search when a goal is encountered and keep on searching until a better goal is found or the state space is exhausted. Such a branch-and-bound algorithm is an extension to uninformed search and prunes all the states that do not improve on the last solution cost. Given that the cost function is monotone, the algorithm always terminates with an optimal solution. The underlying traversal policy for branch-and-bound can be borrowed from either breadth-first search, depth-first search, or best-first search.

Heuristics are either provided by the user, or inferred automatically by generalizing the FSM distance heuristic to include clock variables. The automated construction of the heuristic shares similarities with the ones for metric planning and is involved.

One of the involved differences between real-time reachability and ordinary reachability analysis is the zone inclusion check. In (delayed) duplicate elimination we omit all identical states from further consideration, whereas in real-time model checking we have to check inclusions of the form to detect duplicate states. Once Z is closed under entailment, in the sense that no constraint of Z can be strengthened without reducing the solution set, the time complexity for inclusion checking is linear to the number of constraints in Z.

Subsequently, while porting real-time model checking algorithms to an external device, we have to provide an option for the elimination of zones. Since we cannot define a total order on zones, trivial external sorting schemes are useless in our case. In external breadth-first search we exploit the fact that two states and are comparable only when . This motivates the definition of zone union U, where all zones correspond to the states sharing a common discrete part l, and for all , we have . Duplicate states can now be removed by first sorting with respect to the discrete part l, which will cluster all states, sharing the same l-value, and then performing a one-to-one comparison among all such states. The result of this phase is a file where states are sorted according to the discrete parts l forming duplicate free zone unions. This one-to-one comparison of all the zones for a particular l can only be performed I/O-efficiently when all the states sharing the same l can be read into the main memory. The same approach of internalizing zone unions is available during set refinement with respect to predecessor files. We load both the zone union from the predecessor file and the one in the unrefined file and check for the entailment condition.

The general diagnostic engine (GDE) is a framework for performing model-based diagnostics. It is traditionally exemplified by arithmetic dependency networks, in which we have devices such as adders () and multipliers (). Edges connect the devices as illustrated in Figure 16.18 to an overall graph structure. Variables labeling the edges can be assigned to specific values and the information according to the setting is broadcast within the network. Devices can malfunction and therefore lead to contradictions. The set of possible assignments to the variables is restricted to a small integer range. This implies that all different values can be encoded using only a few bits. A probe of an edge is an assignment to a variable that reflects the supervised background knowledge received in an interaction with the learner. The access to this knowledge is often computationally expensive.

We distinguish two main stages in one iteration of a GDE. On one hand, we have to update the model according to a given probe, and on the other hand, we have to discriminate the candidates for the next probe. In the following we focus on the first issue. GDE is based on an architecture called assumption-based truth maintenance system (ATMS). Besides the dependency network structure, an ATMS maintains database entries , with v being an assignment to a variable and being its justification. A justification is a set of devices that have been used to derive that variable V is assigned to v. Different justifications for a single variable value might exist. Starting with an empty database the learner instantiates variables one after the other. These variables are final, since we have full knowledge of their values. The consequences are drawn with respect to the functionality of the used devices and lead to an assumption on the valuation of the other variables in the network. If the assumption is not confirmed by the learner, we call a value a no-good.

In the example the assignments A to 1, B to 1, C to 1, and D to 1 forces F to equal 2 with justification . The assignment F to 1 is a no-good. Unfortunately, the approach to propagate the values in the network with a simple depth-first search is not sufficient. We need some form of iteration. The new information has to be propagated in the network until no further changes can be achieved, and it has to be offered at every edge of each device node. The database at device node k with degree n for the operation is updated as follows: Take every combination of entries for the variables , calculate with justification , and insert the pair into the database. Especially in large models these efforts are tremendous, such that merging the inputs reveals the bottleneck of the overall propagation.

The set of possible propagations of variables in a discrete domain at a given device consists of instantiations to the incident variables . As seen earlier, BDDs can be utilized to efficiently describe sets of states. In the case of a diagnosis problem a state is a pair consisting of a variable assignment and set of devices that causes the variable to have this particular value.

We have already seen that if we restrict the values to a finite domain, we can represent the Boolean operations Add and Mult with parameters a, b, and c in the form of a BDD. The key idea in using BDDs is that they do not only apply to a single element but to the whole set that is described at the inputs. For example, combining the BDD characterization of the set with the BDD representation of and with the BDD for Mult directly leads to the description of the BDD representation for the set . Moreover, the relational description allows us to apply the BDDs in the reverse direction. For example, the Subtract and Div operators can be obtained by swapping the variable sets a and c in Add and Mult.

Let and be the BDD representations of the different value assignments of the input variables for a device that realizes a Boolean function . The relational product computes the desired output BDD. The other two propagation rules are obtained similarly. The justification of the result can be derived by merging the justifications of the inputs. We extend the result with the influence of the currently operating unit and we only allow to execute the operation if both inputs do not already rely on the unit. Therefore, we build the BDD Result based on the disjunct on all triples of justifications satisfying these additional constraints. As the number of units n and thus the number of bits to encode a justification are big and the power set is exponential in n, we might doubt that this BDD can be constructed, but we explicitly build the BDD for on every index i and build the conjunct for all .

Let be the description of the first input and be the description of the second input. Then we have

The implementation of the proposed diagnosis system based on BDDs is simple. Any diagnostic variable consists of a marker final, a BDD bdd representing all possible value/justification pairs, and the variable sets for addressing value and just. Diagnostic variables are linked to at least two devices to inform the devices if a change to a BDD has been obtained. There are four cases to terminate the propagation:

A top-down proof creates a proof tree, where the node label of each interior node corresponds to the conclusion, and the node labels of its children correspond to the premises of an inference step. Leaves of the proof tree are either axioms or instances of settled theorems. A proof state represents the outer fragment of a proof tree: the top node represents the goal and all leaves representing the subgoals of the proof state. All proven leaves can be discharged, because they are not needed for further considerations. If all subgoals have been solved, the proof is successful.

One estimate for the remaining distance to the goal is the number of internal nodes of the current proof state. An illustrative competitor is the string length of a proof state representation. The number of trees with k internal nodes and the number of strings with length k are both finite, such that for this internal node heuristic and the string length heuristic the number of proof states with fixed heuristic value k are finite.

This is the basis for the design of guided search algorithms with guaranteed progress. At first glance, heuristic search according to the representation size of a theorem seems not to be a good choice, since it exploits very poor knowledge. But even these vague parts of information can speed up computation by magnitudes.

The third heuristic we suggest is the number of open subgoals in the current proof state. This heuristic is the only one that is admissible when we assume that one inference step can close at most one open subgoal at a time. This also proves that the open subgoal heuristic is consistent.

In contrast to the internal node heuristic and the string length heuristic by the limited range of information, the open subgoal heuristic can have infinite plateaus of states with the same estimate value. In this case, greedy best-first search frequently fails to terminate. On the other hand, in regular state spaces, even weaker heuristics may yield fast solutions in greedy search.

In a forward proof, axioms and already proven theorems are combined to generate new theorems. In a backward proof, we start with the theorem to prove, which is step-by-step reduced to new subgoals. With a tactic, basic inference steps are combined to larger case-sensitive and proof-searching rules using axioms, memorized theorems, or assumptions. For increasing performance in some basic object logics, tableau theorem provers have been integrated, but their inference is not generic for all object logics. The inference process is hidden in the auto tactic.

Greedy best-first search expands the states with minimal evaluation function value first. It is attracted by local optima not complete even for finite graphs. In contrast, DFS and BFS are complete since DFS uses global memory to store already proven subgoals, and BFS could omit the pruning of duplicate states.

In a functional implementation of A* (see Alg. 16.3), one input parameter is the heuristic function h(we have not expelled the input and output parameters since the input are all mappings and the function declaration itself is assigned to the output). Furthermore, the successor generation function , goal predicate Goal, and the initial state s are passed to the algorithms as parameters, where the goal function helps filtering the successor states. The priority queue Open is represented by a list of triples , sorted by ascending f-values. For the sake of brevity we have omitted reopening of already expanded nodes on shorter generating paths. If the heuristic function h is consistent, for all , this is no restriction. In this case, on every path the priority f is monotone. All reweighted edges are positive, and the correctness argument of Dijkstra's algorithm applies. All extracted nodes will have correct f-values. The implementation of A* in Algorithm 16.3 uses simultaneous recursion. Keywords and function declarations are set in bold and variables and function calls are set in italics.

In contrast to the imperative setting, in functional A*, insert implements dictionary updates within the set of horizon nodes. If the state is already contained in the priority queue, no insertion takes place, thus avoiding duplicates within the queue. However, since the Closed list of already expanded states is not modeled, even on finite graphs the functional pure heuristic search derivate is no longer complete.

Global expanded node maintenance in Closed is integrated in the pseudo codes of Algorithm 16.3 as follows: Set Closed is supplied as an additional parameter—in A* to the relax function, and in IDA* to the depth function. In A*, Closed is initialized to the empty list at the very beginning, while in IDA*, Closed is reinitialized in each iteration. Instead of (map f visited states are first eliminated by (map f . The dictionary for Closed can be implemented through lists, balanced trees, or low-level hash tables.