Automata Theory for Reasoning About Actions
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 153-158.
© 1999 International Joint Conferences on Artificial Intelligence
Abstract
In this paper, we show decidability of a rather expressive fragment of the situation calculus. We allow second order quantification over finite and infinite sets of situations. We do not impose a domain closure assumption on actions; therefore , infinite and even uncountable domains are allowed. The decision procedure is based on automata accepting infinite trees.
- [Gelfond and Lifschitz, 1993] M. Gelfond and V. Lifs- chitz. Representing action and change by logic pro- grams. J. of Logic Programming, 17:301-322 , 1993 .
- [Liberatore, 1997] P. Liber~tore . The complexity of the language A. Linkoping Electronic Articles in Com- puter and Information Science, 2, 1997.
- [Miller and Shanahan, 1994] R. Miller and M. Shana- han. Narratives in the situation calculus. J . of Logic and Computation (Special Issue on Actions and Pro- cesses), 4(5):513-530, 1994.
- [Pirri and Reiter , 1999] F. Pirri and R. Reiter . Some contributions to the metatheory of the situation cal- culus. J. of ACM, to appear, 1999.
- [Reiter, 1991] R. Reiter. The frame problem in the sit- uation calculus: a simple solution (sometimes) and a completeness result for goal regression . In Vladimir Lifschitz , editor, Artificial Intelligence and Math e- matical Theory of Computation : Papers in Honor of John McCarthy, pages 359-380. Academic Press, San Diego, CA, 1991.
- [Sandewall , 1994] E. Sandewall. Features and Fluents: Th e Representation of Knowledge about Dynamic Sys- tems. Oxford University Press, 1994.
- [Ternovskaia, 1998] E. Ternovskaia. Inductive definabil- ity and the situation calculus. In Transaction and Change in Logic Databases, volume 1472 of Lecture Notes in Computer Science. Springer-Verlag, 1998.
- [Thomas, 1990] W. Thomas. Automata on infinite ob- jects. In J. van Leeuwen, editor, Handbook of Theo- retical Computer Science, pages 134-191. 1990.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
During the last decade, several action formalisms have been developed: [Reiter, 1991, Gelfond and Lifschitz, 1993, Sandewall, 1994, Miller and Shanahan, 1994], to mention a few. The ultimate goal of developing these formalisms is to perform reasoning about actions, which generally amounts to computing answers to queries. More precisely, given action description theory T and query ¢! , we are interested whether <P is a logical con sequence ofT. Obviously, for some theories (in expres sive languages) logical consequence - and thus query answering - will not be decidable. It is important to establish under what restrictions on the language one can obtain an answer for an arbitrary query. We solve this question positively for a rather expressive fragment of the situation calculus 1 . This language is second or der, with quantification over finite and infinite sets of situations. The domain closure axiom for actions is not assumed, therefore infinite and even uncountable action domains are allowed.
Similar work has been done for the action language A proposed in [Gelfond and Lifschitz, 1993]. Liber atore [Liberatore, 1997] studied the complexity of de ciding whether a set of statements in this language is consistent, and specified which restrictions of A lead to tractability and which do not. The author describes a reduction from propositional satisfiability to consistency in A thus showing NP-completeness of the problem. It follows that the entailment problem for the language A is co-NP-complete. Since the language of the situation calculus is more expressive (we allow second order quan tification), the reduction from propositional satisfiability cannot be applied.
1 We use the dialect of the situation calculus developed by the members of the Cognitive Robotics group in Toronto.
Here, we reduce the problem of decidability of the ba sic action theory V (cf. [Pirri and Reiter, 1999]) to the emptiness problem for a tree automaton. The empti ness problem is to determine whether the language ac cepted by a tree automaton is empty. From our construc tion it follows that if the accepted language is empty, then V U { ·<P} is unsatisfiable which is equivalent to the fact that <P is logically implied by V. Since the empti ness problem for tree automata is decidable, the problem V f= <P is decidable as well.
In the following section, we specify the language .C'c of the situation calculus. Section 3 describes the basic action theory V. Section 4 surveys basic definitions of automata theory on infinite trees. Then, in Section 5, we construct a tree automaton corresponding to the basic action theory V. Section 6 is devoted to the main step in the proof of decidability - translating an arbitrary formula in the language of the situation calculus to a tree automaton. Finally, in Section 7, we discuss the implications of this work and outline directions for future research.
2 The Language
We consider a two-sorted version .c·c of the language of the situation calculus with equality and with sorts for ac tions and situations. The primitive non-logical symbols of sort actions consist of variables a, a1, a2 , ... , and con stants A0 , A1 , A2 , ... The primitive non-logical symbols of sort situations consist of variables s, s', s", s, ... , con stant So, binary function do( a, s), where a is an action, s is a situation. This function defines a successor situa tion in terms of a current situation and a performed ac tion. Finitely many unary predicate symbols F1, ... , Fn called fiuents represent properties of the world and have situations as their arguments. We allow quantification over finite and infinite sets of situations, i.e., over unary predicate variables. Sometimes it is convenient to view a situation as a string of performed actions. We shall use binary relation s c s' to represent the prefix relation on the corresponding strings of actions. Below, in Section 3, it will be seen that C is second order definable in terms of function do( a, s) and hence is inessential. The logical symbols of the language are · , ::), 3, = . Other logical connectives and the universal quantifier V are the usual abbreviations . Note that we do not include the predi cate Pass (cf. [Pirri and Reiter, 1999]) . Including it is unproblematic, but would complicate the exposition ..
It is convenient to introduce the following shorthands.
These sentences introduce notations for least and great est fixed points respectively. In these sentences, cl>(X, s) is any formula in the language ,esc with no free variables other than X and s. The following examples demon strate the expressive power of this language. Property "there is a path in the tree of situations where flu ent F holds in infinitely many situations" is express ible by VX,s' J.lY,s' [3s' 3a s' = do( a, s) 1\ [F(s') 1\ X(s') V Y(s')]](s). Formula F1(s) ::) J.lX,s' [3a s' = do( a, s) 1\ F2(s') V Va X(do(a , s'))](s) says that "every occurrence of a situation where fluent F1 holds, is even tually followed by a situation where F2 holds". Prop erty "there is a path in the tree of situations where fluent F holds in every situation" is represented by vx,s' F(s') 1\ [3a s 11 =do( a, s') 1\ X(s")](s).
3 Basic Action Theories
A basic action theory is a set of axioms
where V 1 is the set of foundational axioms for situations, Dss is the set of successor state axioms, one for each fluent, Duna is the set of unique name axioms for actions , and Vs 0 is the description of the initial situation.
First we consider the foundational axioms for the sit uation calculus, V 1. The unique name axioms for situa tions are
The induction principle for situations is
These axioms guarantee that situations compose an in finitely branching tree. Indeed, it can be shown that the class of tree-like structures is completely character ized by the induction principle on situations and unique name assumptions for situations [Ternovskaia, 1998]. The properties of the prefix relation C:: are as follows.
Formula s C:: s' is an abbreviation for s C:: s' V s = s'. Relation s C s' can be defined by
VX {3aX(do(a, s))l\ Vs3a[X(s) ::) X(do(a , s))]::) X(s')}.
We use it for easier formalizations. The foundational axioms for situations, Vf, are (1), (2) and (3).
Successor state axioms , V .. , have the form
Formulart(a, s) (respectively, IF(a,s)) denotes a first order formula specifying the conditions under which flu ent F is true (respectively, false) in the successor sit uation [Reiter, 1991]. The only free variables of these formulae are those among a, s. Function symbol do does not occur in these formulae.
The unique name axioms, Duna, specify that any two actions with different names are not equal. The descrip tion of the initial situation, Vs 0 , is a set of first order sentences that are uniform in So, i.e., contain no situ ation term other than So. We shall call V So the ini tial database. For simplicity, we assume that the initial database is first order and does not contain sentences mentioning no situation term at all. We do not require completeness of Ds 0 ·
4 Tree Automata
Let O" = {Ao, ... , Ak-d be a finite set. Later, in sections 5 and 6, we shall associate the elements of this set with actions. An unlabeled k-ary tree is specified by its set of nodes; each node is a string in 0" 0 · The empty string c corresponds to the root of the tree. If w is a node, then wA; is the i-th son of w. Notice that this set of strings is prefix-closed, and each string uniquely determines a node in the tree. Suppose a finite alphabet I; of labels is given. A k-ary I;-labeled tree t is specified by its set of nodes (the "domain" dom(t) ~ O"*) and a valuation of the nodes (the "labeling function" t : dam( t) -+ I;) . By Tri we denote the set of infinite I;-labeled trees with domain 0" 0 · A subset T of TE will be called a tree lan guage. An example of a tree language is the language

Tv defined in Section 5. This language is determined by the basic action theory V. Another example of a tree language is the language Tq, associated with an arbitrary formula¢ in the language ,e·c. We define Tq, in Section 6.
Both languages, Tv and Tt> , are sets of trees of situations labeled with tuples of fluent values.
Let us review definitions from the general theory of automata on infinite k-ary trees . A Biichi tree automa ton A over alphabet :E is a quadruple A = (Q, Q0 , ~'F) where
- Q is a finite set of states,
- Q0 ~ Q is the set of initial states,
- F ~ Q is the set of final (or accepting) states,
- ~ ~ Q x :E x Qk is the .transition relation .
The transition relation specifies which tuples (q1 , ... , Qk) of states of A can be assumed at the k sons of a node , given the node's label in :E and the state of the au tomaton assumed there . A run of A on a tree t E T¥i is a map r a-· --+ Q with r(c) E Q0, and (r(w) , t(w) , r(wAo) , ... , r(wAk-1)) E ~ ' for w E a-· . In other words, a run is a labeling of the nodes of the t ree t with the states of the automaton A that obeys the transition function. Let C be the proper prefix re lation over a-·. A path through t is a maximal subset of dom(t) linearly ordered by c . If 1r is a path through t, then t j1r denotes the restriction of the function t to the set 1r. Let Qw be the set of infinite strings over the set of states Q. For an w-sequence o = o(O) , o(1) , .. . from Qw , the "infinity set" of o is In( o) = { q E Q J there exist infinitely many n such that o ( n) = q} . The run r is successful if on each path some final state oc curs infinitely often, i.e. , for all paths 1r , In(rj1r)nF #- 0. A Rabin tree automaton over :E has the form A = (Q, Qo , ~ ' n) , where Q, qo , ~ are as before , and n = {(L1 , Ul), ... , (Ln, Un)} is a collection of "accepting pairs" of state sets L; , U; ~ Q. A run r of the Rabin automaton A is successful if for all paths 1r there exists an i E {1 , ... , n} with In(rj1r)nL; = 0 and In(rj1r)nU; #- 0.

A tree t E T¥i is accepted by a Biichi, respectively Ra bin tree automaton A, if some run of A is successful in the corresponding sense. A set T ~ T¥i is Biichi recog nizable, respectively Rabin recognizable, if it consists of the trees accepted by a Biichi , respectively Rabin tree automaton . Since any Biichi tree automaton may be re garded as a Rabin tree automaton (set n = {(0, F)}) , any Biichi recognizable set of infinite trees is Rabin rec ognizable. Both Biichi and Rabin tree automata are closed under union, intersection and projection. The fa mous Rabin complementation theorem holds for Rabin tree automata, but fails for Biichi tree automata. More information about tree automata can be found in the excellent survey [Thomas , 1990).
Example 1 Consider the infinite labeled tree repre sented in Figure 1. This tree has the following property. The label of the root is 0. The son wA0 of every node w is always labeled with 1. If the label of a current node w is 1 (0 , respectively) , then the label of the node wA1 is 0 (1 , respectively). A deterministic tree automaton ac cepting this tree is represented in Figure 2. The initial state is Q1, and the accepting state is Q2 · Notice that we could rename state q1 of the automaton as 0 and state q2 as 1. The input label then would always coincide with the current state of the automaton. An automaton hav ing this property is called input-free. The automata from Section 5 are input-free. This is not the case, however, for automata considered in Section 6.
5 Translating 1) t o a Tree Automaton
In the remaining part of the paper, we shall consider the trees of situations. The set of nodes, the domain, of such a tree is the set of strings of actions . The empty string c corresponds to the initial situation 50 . If w is a string representing situation s , then string wA;, where A; is an action, represents do( A; , s) . Let the language include n fluents , then the alphabet of labels :En is the set of all tuples of length n over alphabet {0, 1}. Position i of the tuple corresponds to the i-th fluent, 1 :S i :S n . The labeling function maps each node of the tree , a situation, to an element of :En.
In this section, we demonstrate a connection between the structures of the basic action theory V and the trees accepted by a Biichi tree automaton. The main difficulty in proving such a connection is that the universe of ac tions may be infinite, or even uncountable. To approach this problem, we first introduce a structure .U of V such that if V is satisfiable then this structure is a model of V. Let a-A = { A0 , ... , Ak _1} be the set of all constants of sort action in the language .esc. Let .U be a structure with the universe of actions UA = {Ao,A~, .. . , Ak-l , A~_tJ. The universe of situations, Us, is constructed by apply ing function do starting from the initial situation. The basic action theory V is satisfiable if and only if f:u V.
Given a-A = {A0 , ... , Ak-d , we consider infinite 2Ja-AJ-ary trees where the domain (i .e., the set of nodes) is the set of strings over a- = {Ao, A~, ... , Ak-1, A~_tJ. Let :E be { 0, 1}, :En be the n-fold Cartesian product of :E. Every tuple (V1 , ... , Vn) of sets of situations yields a tree t(V1 , ... , Vn) that labels each node wE a-· with tu ple (cv,(w), ... ,cvn(w)) E :En , where cv(w) is the char acteristic function of V . Notice that each fluent F can be seen as the set of situations where it is true. Thus, every tuple (F1 , ... , Fn) of fluents yields a 2ja-A J-ary tree tv(F1 , ... , Fn) labeled with the elements of :En. Notice further that the characteristic function cF(w) ofF spec ifies whether fluent F holds in the situation represented by string w . The characteristic function for each fluent is determined by successor state axioms, V 80 , and by the initial database , 'Ds 0 · With every set of axioms 'D, we shall associate a Biichi tree automaton Av that accepts a tree language Tv(FI, ... , Fn)· This automaton depends on the description of the initial situation 'Ds 0 and the choice of successor state axioms 'D 33 ·
Theorem 1 Let U be the model of 'D defined above. With every set of axioms 'D one can effectively associate a tree Biichi automaton Av labeled with the elements of :En such that
ProofWe shall construct a Biichi tree automaton Av that accepts trees labeled with tuples (cp 1 (w), ... , cpJw)), for each node w. The set of states Q of Av is the set of all possible n-tuples over { 0, 1} .
First, we define the set of initial states Q0 . Note that we have restricted 'Ds 0 to be a collection of ground for mulae. Find the set of satisfying truth assignments for 'Ds 0 , or determine that no such assignment exists. In the latter case 'D is unsatisfiable, and Av is an automa ton without final states. This means that the set of trees it accepts is empty. The set of truth assignments corre sponds to the set of tuples (cp 1 (c) , ... , cp,. (c)) of char acteristic functions specifying which fluents hold in the initial situation. Each such tuple is an element of Qo .
Second, we define the transition relation ~ ~ Q x :En x Q 2 1 11 AI. This relation specifies what tuples of automaton states may be assumed at the 21 u A I sons of the node , i.e., what states (tuples of fluent values) are reached by performing each action A; . A transition exists if and only if the state of the automaton is the same as the label of the current node. It is easy to see that the set of all truth assignments satisfying successor state axioms determines the transition relation. The computability of this set of truth assignments is guaranteed by the definition of .c;c and the form of 1+, ,-. If this set does not exist we, again, construct Av so that it accepts the empty language.
Example 2 Suppose 'D includes two successor state ax IOms:
The transition function is determined by the truth as signments that satisfy the successor state axioms. For example, suppose F1 is false and F2 is true in a situ ation. This corresponds to the label (0, 1) of the tree of situations and to a state of the automaton with the same name. (Recall that all automata considered in this section are input-free.) Now we have to specify which tuples of states may be assumed at the four sons of this node. Suppose Ao is performed. According to the suc cessor state axioms, F1 will be true and F2 will be false in the successor situation. This corresponds to state (1, 0) of the automaton. We map all actions different from A0 to the action AfJ . Thus, whenever a # A0 , we consider the transition from node w to node wAfJ . This transi tion leads to state (0, 1) if AfJ equals A1 and to state
(1, 1) otherwise. For actions A1 and A~ the construc tion is similar. A tree automaton corresponding to these successor state axioms is represented in Figure 3.

Now we continue defining Av. The set F of final states of this automaton coincides with the set of all states, Q. We impose Biichi acceptance condition: a tree over :En is accepted by Av if there is a run such that in all possible paths some final state occurs infinitely often. We claim that f=u 'D if and only if Av accepts Tv(FI, ... , Fn) ·
Suppose F=u 'D. Then 'DJ is satisfied by 2luAI-ary trees of situations; 'D so specifies the set of initial states of Av ; and 'D 33 is satisfied by the truth assignment which determines the transition relation ~ of the automaton. The number of states of Av is finite . Therefore the only way to obtain infinite computations is by looping. Since all states of Av are accepting, all paths starting at one of the initial states contain at least one accepting state infinitely often. Therefore Av accepts trees labeled with tuples (cp 1 (w), ... , cp,. (w)), for each node w. The set of these trees is Tv(FI, .. . ,Fn)·
Suppose Av accepts all trees from Tv(F1 , ... , Fn)· These 21 u A 1-ary trees satisfy the foundational axioms 'D J . The label (cp 1 ( w), ... , cpJ w)) of each node w deter mines fluent values in the corresponding situation. The transition relation for Av is represented by a set of tuples which determines the set of satisfying truth assignments for 'D 33 . The set of initial states of Av specifies the initial database 'Ds 0 · Therefore, 'D is satisfiable, and it follows that F=u 'D. D
6 Translating 4> to a Tree Automaton and Decidability of V
With every formula </J in the language .c_sc, we shall as sociate a Rabin tree automaton Aq, . This automaton ac cepts labeled 21 u A 1-ary trees determined by the formula <P if and only if f=u </;, where U is a structure constructed as in the previous section. Notice that it is sufficient to consider structures of this form - we are interested in satisfying D and ¢J simultaneously. For easier exposition, we restrict to the case where <T.A = {Ao, Ad are the only actions occurring in D. The proof generalizes easily for the case with any number of actions.
Let ¢J [F1, .. . , Fm) be a formula in the language of the situation calculus £ 8 c with fluents F1, ... , Fm, where m < n and n is the total number of fluents.
Theorem 2 Let <T.A = {A0 , Al}. Let i1. be the model of D defined in section 5. With every formula ¢J[F1, ... , Fm) in the language £ 8 c one can effectively associate a I:m tree Rabin automaton A¢ such that for all F1 , ... , Fm ~ {Ao, A~, A1, AD*,
Proof In the proof of this theorem we use techniques similar to those used in the proof of Rabin's result about the decidability of S2S, the second order monadic logic of two successors.
For every formula ¢J we construct an equivalent for mula c/J' in a (formally first order) language with binary predicates ~ , Succ0 , Succ~ , Succ1, Succ~, with variables ranging over subsets of {Ao ,A~,A1,AD* , with the ob vious interpretation of ~, and with
Carry out the following steps, starting with a given for mula ¢J in the language £·c.
- (i) Eliminate superpositions of "do" by introducing additional variables of sort situations. For example,
- (ii) Eliminate universal and existential quantification over actions by using conjunctions and disjunctions, re spectively. For example, Vs Va F(do(a, s)) becomes
- (iii) Eliminate occurrences of action symbols other than as arguments of function do. For example,
- (iv) Eliminate the symbol So by using the property that no situation is a proper prefix of So . For example,
We arrive at a. formula with atomic formulae of the form s = s', do(A;,s) = s', and F(s) only.
For the remaining step we use the shorthands
(there is exactly one proper subset of F).
(v) Eliminate variables ranging over situations and function do( a, s) by using relations Sing and Succ. For example,
We obtain a formula c/J' equivalent over tree-like struc tures to the given formula ¢J in the following sense: if i1. is the structure with the domain of actions { A0 , A~, A 1, A~}, as defined in the previous section, and if ti' = ( {Ao, A~, A1, AD ·, ~, succo, succ~, succ1, succ~), then f= u ¢J if and only if f= U' c/J'.
For each formula c/J' in the language with binary predi cates ~, Succ0 , Succ~, Succ1, Succ~, one can effectively construct a tree automaton A¢' satisfying the conditions of the claim. We show this by induction over c/J'.
For atomic formulae the construction is easy. Let I: 2 = {0, 1} x {0, 1}. In this case, each node w is la beled with tuple (cp(w) , cp,(w)). For F ~ F' we need a tree automaton A that accepts a I: 2 -tree t if and only if t avoids the label (0, 1), i.e., t(w) =f. (0, 1) for all nodes w. This is achieved by an automaton with a single state q (which is initial and final) and transition (q, a, q) for all a =f. (0 , 1) .
For Succ;(F, F') the automaton A; has three states, q0 , q1, q2 , where q0 is the initial state and q2 is the final state; the transitions are (qo,(O,O),qo), (qo,(1 , 0),qi), (q1,(0, 1),qz),(qz,(O,O),q2)· Automaton A; accepts t if and only if there exist a node w E {A0 , A~,A1 ,Ai}* such that t(w) = (1,0), t(wA;) = (0, 1) and t(w') = (0, 0) for any other node w'. In other words, A; accepts if and only if there is a situations such that F holds ins, F' holds in do(A;, s), and these fluents do not hold anywhere else. In the case if there are more than two fluents, the construction is es sentially the same except for each additional fluent , say F;, we replace each transition with two transitions, one with 1 on the i-s position, one with 0. The induction step for c/J' = 'lj; V v, c/J' = :JX 'lj; and c/J' = ·'!f; follows from the fact that (nondeterministic) tree automata are closed under union, projection and complementation. D
Recall that theory T in language £ is decidable if and only if there is an algorithm to determine whether any given sentence ¢J of£ is a logical consequence ofT.
Theorem 3 The basic action theory D in language _esc is decidable.
Proof We shall use the fact that D f= <P if and only if D U -.<jJ is unsatisfiable. From the construction of Av and A, cf>, it follows that
Every Biichi tree automaton is also a Rabin tree au tomaton. Rabin tree automata are closed under comple mentation and intersection. The emptiness problem for Rabin tree automata is decidable. It follows that there is an algorithm to determine D f= <P for an arbitrary <P in [_JC' i.e., theory D in language esc is decidable. 0
7 Conclusions
We have proven the decidability of the basic action the ory D in the second order language of the situation cal culus. This language allows one to reason about quite sophisticated properties of the trees of situations, such as, for example, "there is a path in the tree of situations where fluent F holds in infinitely many situations" or "every occurrence of a situation where fluent F1 holds, is eventually followed by a situation where fluent F2 holds". Reasoning about such properties is especially important when one has to address the verification of high-level programs for robotics.
Of course, expressiveness never comes for free. The decision procedure described in this paper is non elementary. Each level of negation in the given formula -.<jJ requires a corresponding complementation of a Rabin automaton and hence an at least exponential blow-up in the size of the query. A nice improvement of our result would be a decision procedure of elementary time com plexity (i.e., of time complexity bounded by the compo sition of a fixed number of exponential functions), or a proof that no such procedure exists. This direction of research is interesting because in practice queries tend to be relatively small.
Our decision procedure can be easily generalized for the case of concurrent actions. Each transition to a son of a node would be performed if a corresponding group of concurrent actions is executed. It is also straightfor ward to incorporate actions with non-deterministic ef fects. This would amount to redefining the automaton Av from Section 5 as non-deterministic. Introducing in direct effects is a more complicated problem. Extending our decision procedure to handle ramifications would be an interesting exercise.
For many practical problems we need to study the entailment of restricted classes of queries. Such queries might be, for example, those expressible using fixed point operators J.L and 11, or those where set quantifiers refer to chains in trees of situations (i.e., sets of situations linearly ordered by the prefix relation c:), or . to paths of situations (i.e., maximal chains). Developing decision procedures for these subproblems would be useful. The impact of incorporating more information about the the ory D on the complexity of the decision procedure is also of interest. Another intriguing direction of research is to further investigate the boundary between decidable and undecidable fragments of the situation calculus.
In our proofs, we have used automata on infinite trees. To our knowledge, this is the first time that automata theory has been applied to the problems of reasoning about actions. We consider automata-theoretic tech niques useful for the following reasons. First , automata bear 3{1. obvious relation to action theories. Transition diagrams for tree automata are closely connected to suc cessor states axioms specifying the effects of actions. Second, automata-theoretic techniques provide the only known methods of obtaining elementary time decision procedures for some very expressive logics. Therefore, they bear great potential for automating reasoning.
Acknowledgments
Thanks to Ray Reiter and to the anonymous referees for helpful comments.
@inproceedings{ijcai1999p23,
title = {Automata Theory for Reasoning About Actions},
author = {Ternovskaia, Eugenia},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {153--158},
year = {1999},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1999/23},
}
TY - CPAPER TI - Automata Theory for Reasoning About Actions AU - Ternovskaia, Eugenia T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 153 EP - 158 UR - https://ijcai.org/proceedings/1999/23 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: