On the role of automated theorem proving in the compile-time derivation of concurrency

A recent trend in program development is to derive correct implementations from program specifications by the application of a formal calculus, a programming methodology. The application of formal rules lends itself to automation. We investigate the automation of one part of a methodology for programming with concurrency. In this methodology, concurrency is derived by transforming the sequential execution of a program into an equivalent concurrent execution on the basis of formal transformation rules. Such rules can be interpreted as theorems of semantic equivalences. The mechanical certification of these theorems would significantly enhance the reliability of the methodology. The following is an initial exploration of this problem applied to a certain class of programs: sorting networks. We present an implementation of a part of the underlying semantic theory in Boyer and Moore's mechanized logic, and report on the mechanical proof of a transformation that derives concurrency for an insertion sort.     

Sur les générateurs algébriques et linéaires

Résumé Nous étudions certaines propriétés des générateurs algébriques et linéaires. Nous montrons que le langage algébrique E engendré par la grammaire: S aSbSc + d domine tous les langages algébriques par applications séquentielles fidèles. Nous en déduisons que pour tout langage algébrique L et tout générateur algébrique L, il existe une transduction rationnelle fonctionnelle et fidèle telle que L=(L). Ce résultat, qui n'est pas vérifié pour la famille, Lin, des langages algébriques linéaires, nous permet de montrer qu'aucun générateur algébrique n'appartient à la famille EDTOL. Enfin, nous établissons que si L est un générateur linéaire, L # est un générateur séquentiel pour Lin.

---

Algebraic and linear generators

Summary We study some properties of algebraic and linear generators. We show that the algebraic language E generated by the grammar: S aSbSc + d dominates every algebraic language by faithful sequential mappings. We deduce that, for every algebraic language L and every algebraic generator L, there exists a faithful rational function such that L=(L). This result, which does not hold for the family of linear languages, permits us to show that no algebraic generator belongs to the family EDTOL. Also, we prove if L is a linear generator then L # is a sequential generator for Lin.

     

On parsing two-level grammars

Summary Making use of the fact that two-level grammars (TLGs) may be thought of as finite specification of context-free grammars (CFGs) with infinite sets of productions, known techniques for parsing CFGs are applied to TLGs by first specifying a canonical CFG G — called skeleton grammar — obtained from the cross-reference of the TLG G. Under very natural restrictions it can be shown that for these grammar pairs (G, G) there exists a 1 — 1 correspondence between leftmost derivations in G and leftmost derivations in G. With these results a straightforward parsing algorithm for restricted TLGs is given.     

Formalizing Synthetic Domain Theory

Synthetic Domain Theory (SDT) is a constructive variant of Domain Theory where all functions are continuous following Dana Scotts idea of domains as sets. Recently there have been suggested more abstract axiomatizations encompassing alternative notions of domain theory as, for example, stable domain theory.In this article a logical and axiomatic version of SDT capturing the essence of Domain Theory à la Scott is presented. It is based on a sufficiently expressive version of constructive type theory and fully implemented in the proof checker Lego. On top of this core SDT denotational semantics and program verification can be – and in fact has been – developed in a purely formal machine-checked way.The version of SDT we have chosen for this purpose is based on work by Reus and Streicher and can be regarded as an axiomatization of complete extensional PERs. This approach is a modification of Phoas complete -spaces and uses axioms introduced by Taylor.     

A general proof rule for procedures in predicate transformer semantics

Summary A proof rule for the procedure call is derived for procedures with value, result and value-result parameters. It is extended to procedures with unrestricted global variables and to recursive procedures. Like D. Gries's proof rule, it is based on the substitution rule for assignment. However, it is more general and much simpler to apply. Assume that {U} S {V} has been proved about the procedure body S. The proof rule for determining whether a call establishes predicate E is based on finding an adaptation A satisfying AV E, where E is derived from E by some substitution of parameters.     

On the usefulness of bifaithful rational cones

Roughly, a faithful (resp. bifaithful) rational transduction is a non deterministic finite state mapping that does not decrease (resp. alter) the length of words by very much. We introduce the notion of stronglyf-saturated language:L is stronglyf-saturated if and only if for any languageL, from which we can obtainL by faithful rational transduction, for any languageL, image ofL by a faithful rational transduction, there exists a bifaithful rational transduction such thatL is the image ofL . We prove that no quasirational language and no language in the substitution closed rational cone generated by bounded languages is stronglyf-saturated. Conversely, we establish that a language such as , very low in the hierarchy of algebraic languages, is stronglyf-saturated thus is not a quasirational language. We also establish that any commutative quasi rational language over two letters is rational.     

Proof Reflection in Coq

We formalize natural deduction for first-order logic in the proof assistant Coq, using de Bruijn indices for variable binding. The main judgment we model is of the form d[:], stating that d is a proof term of formula under hypotheses it can be viewed as a typing relation by the Curry–Howard isomorphism. This relation is proved sound with respect to Coq's native logic and is amenable to the manipulation of formulas and of derivations. As an illustration, we define a reduction relation on proof terms with permutative conversions and prove the property of subject reduction.     

Behaviour Synthesis of the Erect Stance for a Biped Control

In this paper we use free fall approach to develop a high level control/command strategy for a bipedal robot called BIPMAN, based on a multi-chain mechanical model with a general control architecture. The strategy is composed of three levels: the Legs and arms level, the Coordinator level and the Supervisor level. The Coordinator level is devoted to controlling leg movements and to ensure the stability of the whole biped. Actually perturbation effects threaten the equilibrium of the human robot and can only be compensated using a dynamic control strategy. This one is based on dynamic stability studies with a center of mass acceleration control and a force distribution on each leg and arm. Free fall in the gravity field is assumed to be deeply involved in the human locomotor control. According to studies of this specific motion through a direct dynamic model,the notion of equilibrium classes is introduced. They allow one to define time intervals in which the biped is able to maintain its posture. This notion is used for the definition of a reconfigurable high level control of the robot.     

Some results in tree automata

Summary The following three results concerning tree automata are presented in this paper. (1) Rounds has presented the following open problem: For every recognizable setR, can we construct a deterministic finite-state transformation recognizingR? We show that this is not possible, in fact, even for a local set. However, the following is true: For every recognizable setR there is an inverse projectionR effectively obtained such thatR is recognized by a deterministic finite-state transformation. (2) Martin and Vere in their study of tree automata leave open the question of whether Generalized Syntax Directed Transductions (GSDT's) are closed under Arden's transformation or Greibach's transformation, and conjecture that they are not. We prove that this conjecture is true. It is also shown that GSDT's are not closed under transformation to LR(k) grammars. (3) Peters and Ritchie have shown that if, in a grammar where the generative rules are context-free, there are recognition rules which are context-sensitive, the language recognized is still context-free. A tree-automata-oriented proof is given by Rounds. We show that a similar result holds also for right linear grammars, i.e., if the generative rules are right linear, then using context-sensitive rules for recognition, one can still recognize only regular languages. Some other related results concerning context-sensitive extensions of subclasses of context-free languages are also presented.This work was partially supported by NSF Grant GJ27, U.S. Army Research Office, Durham (DA-31-124 ARO(D)-98), and NSF Grant GS-2509.A present on leave at The Institute for Advanced Study, Princeton, N.J.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

More Church–Rosser Proofs

The proofs of the Church–Rosser theorems for , , and reduction in untyped -calculus are formalized in Isabelle/HOL, an implementation of Higher Order Logic in the generic theorem prover Isabelle. For -reduction, both the standard proof and Takahashi's are given and compared. All proofs are based on a general theory of commutating relations that supports an almost geometric style of reasoning about confluence diagrams.     

Mechanizing set theory

Fairly deep results of Zermelo-Frænkel (ZF) set theory have been mechanized using the proof assistant Isabelle. The results concern cardinal arithmetic and the Axiom of Choice (AC). A key result about cardinal multiplications is =, where is any infinite cardinal. Proving this result required developing theories of orders, order-isomorphisms, order types, ordinal arithmetic, cardinals, etc.; this covers most of Kunen, Set Theory, Chapter I. Furthermore, we have proved the equivalence of 7 formulations of the Well-ordering Theorem and 20 formulations of AC; this covers the first two chapters of Rubin and Rubin, Equivalents of the Axiom of Choice, and involves highly technical material. The definitions used in the proofs are largely faithful in style to the original mathematics.     

Substitution of grammar forms

Summary Given grammar forms F and F, the grammar form Sûb (F, Ft') is defined as that obtained by substituting the start variable of F for every occurrence of a terminal in F. The main result is that if F is a nontrivial grammar form, then the grammatical family defined by Sûb (F, F) is the set of languages obtained by substituting languages in the family defined by F into the family defined by F. Thus the substitution of one grammatical family into another is a grammatical family. It follows as a corollary that the full AFL generated by a grammatical family is a grammatical family.This research was supported in part by a Guggenheim fellowship and by NSF Grant No. 42306.     

Logic programming and Σ-programming

We consider the main similarities and dissimilarities between logic programming and -programming. Particular emphasis is placed on efficient implementation of -programs. Algorithms that translate logic programs into -programs and back are given.Translated from Kibernetika, No. 1, pp. 67–72, January–February, 1989.     

States and the free orthogonality monoid

Let (X, #) be an orthogonality space such that the lattice C(X, #) of closed subsets of (X, #) is orthomodular and let (, ) denote the free orthogonality monoid over (X, #). Let C₀(, ) be the subset of C(, ), consisting of all closures of bounded orthogonal sets. We show that C₀(, ) is a suborthomodular lattice of C(, ) and we provide a necessary and sufficient condition for C₀(, ) to carry a full set of dispersion free states.The work of the second author on this paper was supported by National Science Foundation Grant GP-9005.     

TMPR: A tree-structured modified problem reduction proof procedure and its extension to three-valued logic

This paper deals with automated deduction for classical and partial logics, especially for the three-valued logic L3, which has been introduced, for example, in the study of natural language semantics. Based on ideas from a Plaisted's Gentzen style system for classical two-valued logic, we present a new tree-structured proof procedure (TMPR) together with a new completeness proof using proof transformation techniques and some improvements including the generation and use of lemmata. TMPR extends SLD-resolution with a Prolog-style backward chaining to full first-order logic by a controlled use of case analysis. This is done without having to extend negative goals needed, for example, for model elimination. A classification of TMPR, model elimination and related calculi in a common tableau framework is given. Thereafter, we present our extension of the TMPR proof procedure to L3 and show its soundness and completeness. As a side result, a TMPR proof system for the four-valued logic L4 is given. Finally, the restriction of TMPR to L3-Horn clauses is considered, and, additionally, an idea for similarly extending model elimination and related systems to L3 (and L4) is illustrated.This work is supported by the KI-Verbund NRW, founded by the Ministry for Science and Research of North Rhine Westphalia and by the Deutsche Forschungs Gemeinschaft in the scope of the research topic Deduktion, and is an extended version of a talk held at the German-Japanese Workshop on Logic and Natural Language (23–25 October 1990, in Kyoto, Japan).     

Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity

Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(₁... _N ) is attained, given the cost f( _i ) of a message ₁... _N . Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function f( _i ) – K(₁... _N ) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.     

Types with intersection: An introduction

This paper is an informal introduction to the theory of types which use a connective for the intersection of two types and a constant for a universal type, besides the usual connective for function-types. This theory was first devised in about 1977 by Coppo, Dezani and Sallé in the context of-calculus and its main development has been by Coppo and Dezani and their collaborators in Turin. With suitable axioms and rules to assign types to-calculus terms, they obtained a system in which (i) the set of types given to a term does not change under-conversion, (ii) some interesting sets of terms, for example the solvable terms and the terms with normal form, can be characterised exactly by the types of their members, and (iii) the type-apparatus is not so complex as polymorphic systems with quantifier-containing types and therefore probably not so expensive to implement mechanically as these systems.There are in fact several variant systems with different detailed properties. This paper defines and motivates the simplest one from which the others are derived, and describes its most basic properties. No proofs are given but the motivation is shown by examples. A comprehensive bibliography is included.     

On reducing the number of stack symbols in a PDA

Two transformations are presented which, for any pushdown automaton (PDA)M withn states andp stack symbols, reduce the number of stack symbols to any desired numberp greater than one. The first transformation preserves deterministic behavior and produces an equivalent PDA witho(np/p) states. The second construction, using a technique which introduces nondeterminism, produces an equivalent PDA withO(np/p) states. Both transformations are essentially optimal, the former among determinism-preserving transformations, the latter among all transformations.This research was supported in part by the National Science Foundation under Grants MCS 76-10076 and MCS 76-10076A01 and by the Stiftung Volkswagenwerk under Grant No. II/62 325.     

A dialectical model of assessing conflicting arguments in legal reasoning

Inspired by legal reasoning, this paper presents a formal framework for assessing conflicting arguments. Its use is illustrated with applications to realistic legal examples, and the potential for implementation is discussed. The framework has the form of a logical system for defeasible argumentation. Its language, which is of a logic-programming-like nature, has both weak and explicit negation, and conflicts between arguments are decided with the help of priorities on the rules. An important feature of the system is that these priorities are not fixed, but are themselves defeasibly derived as conclusions within the system. Thus debates on the choice between conflicting arguments can also be modelled.The proof theory of the system is stated in dialectical style, where a proof takes the form of a dialogue between a proponent and an opponent of an argument. An argument is shown to be justified if the proponent can make the opponent run out of moves in whatever way the opponent attacks. Despite this dialectical form, the system reflects a declarative, or relational approach to modelling legal argument. A basic assumption of this paper is that this approach complements two other lines of research in AI and Law, investigations of precedent-based reasoning and the development of procedural, or dialectical models of legal argument.Supported by a research fellowship of the Royal Netherlands Academy of Arts and Sciences, and by Esprit WG 8319 Modelage.