Well-founded semantics and stratification for ordered logic programs

This paper present an extension of traditional logic programming, called ordered logic (OL) programming, to support classical negation as well as constructs from the object-oriented paradigm. In particular, such an extension allows to cope with the notions of object, multiple inheritance and non-monotonic reasoning. The contribution of the work is mainly twofold. First, a rich wellfounded semantics for ordered logic programs is defined. Second, an efficient method for the well-founded model computation of a meaningful class of ordered logic programs, called stratified programs, is provided.     

Stochastic process semantics for dynamical grammars

We define a class of probabilistic models in terms of an operator algebra of stochastic processes, and a representation for this class in terms of stochastic parameterized grammars. A syntactic specification of a grammar is formally mapped to semantics given in terms of a ring of operators, so that composition of grammars corresponds to operator addition or multiplication. The operators are generators for the time-evolution of stochastic processes. The dynamical evolution occurs in continuous time but is related to a corresponding discrete-time dynamics. An expansion of the exponential of such time-evolution operators can be used to derive a variety of simulation algorithms. Within this modeling framework one can express data clustering models, logic programs, ordinary and stochastic differential equations, branching processes, graph grammars, and stochastic chemical reaction kinetics. The mathematical formulation connects these apparently distant fields to one another and to mathematical methods from quantum field theory and operator algebra. Such broad expressiveness makes the framework particularly suitable for applications in machine learning and multiscale scientific modeling.      

Recursive descent parsing for Boolean grammars

The recursive descent parsing method for the context-free grammars is extended for their generalization, Boolean grammars, which include explicit set-theoretic operations in the formalism of rules and which are formally defined by language equations. The algorithm is applicable to a subset of Boolean grammars. The complexity of a direct implementation varies between linear and exponential, while memoization keeps it down to linear. Supported by the Academy of Finland under grant 118540.     

Graph grammars and operational semantics

Transformations of graphlike expressions are called correct if they preserve a given functional semantics of the expressions. Combining the algebraic theories of graph grammars (cf. [10]) and programming language semantics (cf. [1]) it will be proved that the correctness of transformation rules carries over to the correctness of derivations via such rules. Applying this result to LISP we show that a LISP interpreter represented by a graph grammar is correct with respect to the functional semantics of graphlike LISP expressions.     

A game-theoretic characterization of Boolean grammars

We obtain a simple, purely game-theoretic characterization of Boolean grammars [A. Okhotin, Boolean grammars, Information and Computation, 194(1) (2004) 19–48]. In particular, we propose a two-player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and offers a promising new connection between game theory and formal languages.     

Bridging the gap between formal semantics and implementation of triple graph grammars

The correctness of model transformations is a crucial element for model-driven engineering of high-quality software. A prerequisite to verify model transformations at the level of the model transformation specification is that an unambiguous formal semantics exists and that the implementation of the model transformation language adheres to this semantics. However, for existing relational model transformation approaches, it is usually not really clear under which constraints particular implementations really conform to the formal semantics. In this paper, we will bridge this gap for the formal semantics of triple graph grammars (TGG) and an existing efficient implementation. While the formal semantics assumes backtracking and ignores non-determinism, practical implementations do not support backtracking, require rule sets that ensure determinism, and include further optimizations. Therefore, we capture how the considered TGG implementation realizes the transformation by means of operational rules, define required criteria, and show conformance to the formal semantics if these criteria are fulfilled. We further outline how static and runtime checks can be employed to guarantee these criteria.     

Paramodulation with Well-founded Orderings

For many years, all existing completeness results for Knuth–Bendixcompletion and ordered paramodulation required the term ordering to be well-founded, monotonic and total(izable) on ground terms.Then, it was shown that well-foundedness and the subterm propertywere enough for ensuring completeness of ordered paramodulation.Here we show that the subterm property is not necessary either.By using a new restricted form of rewriting, we obtain a completenessproof of ordered paramodulation for Horn clauses with equality,where well-foundedness of the ordering suffices. Apart fromthe theoretical significance of this result, some potentialapplications motivating the interest of dropping the subtermproperty are given. The proof of the results included in thisarticle, being still technical in some parts, is pretty muchshorter and easier to read than the one we have in the preliminaryversion of this work presented at the CADE, 2002 conference(Bofill, and Rubio, 2002, CADE, Vol. 2392 of LNAI, pp. 456–470).     

Parsers for indexed grammars

Three classes of parsable indexed grammars are defined. The new parsing mechanisms are derived by extending those that have been most successful for contextfree grammars, the LR and LL algorithms. Design criteria for the new grammar classes include membership decidability and unambiguity. We show that all three parsers operate in linear time for at least some grammars in our new classes. One of our new classes generates all the deterministic contextfree languages, along with some noncontextfree languages. We also show that the flag strings generated by indexed grammars are regular sets. This is done by showing that they can be generated by regular canonical systems.     

On Non-axiomatizability of Superintuitionistic Predicate Logics of Some Classes of Well-founded and Dually Well-founded Kripke Frames

The article presents general results on non-axiomatizabilityfor superintuitionistic predicate logics. In particular, thelogics of all well-ordered, all dually well-ordered, and alldually well-founded Kripke frames (in the semantics with nestedand with constant domains) are -hard, and the logic of all Kripke frames of finite heightis not recursively axiomatizable (although it is known to be -arithmetical). A resulton Kripke-incompleteness is stated as well.     

Apex graph grammars and attribute grammars

Summary Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).     

Well-founded and stationary models of logic programs

We investigate the class ofstationary or partial stable models of normal logic programs. This important class of models includes all (total)stable models, and, moreover, thewell-founded model is always its smallest member. Stationary models have several natural fixed-point definitions and can be equivalently obtained as expansions or extensions of suitable autoepistemic or default theories. By taking a particular subclass of this class of models one can obtain different semantics of logic programs, including the stable semantics and the well-founded semantics. Stationary models can be also naturally extended to the class of all disjunctive logic programs. These features of stationary models designate them as an important class of models with applications reaching far beyond the realm of logic programming.Partially supported by the National Science Foundation grant #IRI-9313061.     

约束逻辑程序的良基模型研究

在介绍约束逻辑程序的定义、可满足性及其稳定模型等概念的基础上,研究约束逻辑程序的正文字展开方法和约束原子的正文字前缀幂集方法,对展开前后逻辑程序的等价特性进行逻辑证明。分析正规逻辑程序良基模型的构建方法,以求得经展开得到的等价正规逻辑程序的最小不动点为切入,给出简单约束逻辑程序交替不动点的良基语义模型。经推理证明,该良基模型是合理的,用该模型的构建方法将约束逻辑程序转化为正规逻辑程序也是可行的。     

Extending Lambek grammars to basic categorial grammars

Pentus (1992) proves the equivalence of LCG's and CFG's, and CFG's are equivalent to BCG's by the Gaifman theorem (Bar-Hillel et al., 1960). This paper provides a procedure to extend any LCG to an equivalent BCG by affixing new types to the lexicon; a procedure of that kind was proposed as early, as Cohen (1967), but it was deficient (Buszkowski, 1985). We use a modification of Pentus' proof and a new proof of the Gaifman theorem on the basis of the Lambek calculus.     

Lower bounds for context-free grammars

Ellul, Krawetz, Shallit and Wang prove an exponential lower bound on the size of any context-free grammar generating the language of all permutations over some alphabet. We generalize their method and obtain exponential lower bounds for many other languages, among them the set of all squares of given length, and the set of all words containing each symbol at most twice.     

Normal forms for context-sensitive grammars

Summary In this paper, we mainly study the relation between scattered context grammars, which are an example for regulated context-free rewriting devices, and context-sensitive grammars. Emphasis is laid upon both normal form characterizations of context-sensitive grammars and an argument in how far scattered context grammars are stronger, with respect to generative capacity than unordered scattered context grammars.Parts of this paper have been presented at the Conference on Formal Languages and Programming Languages, University of Dortmund, Germany, March 29–31, 1973.     

From algebraic semantics to denotational semantics for Verilog

This paper considers how the algebraic semantics for Verilog relates with its denotational semantics. Our approach is to derive the denotational semantics from the algebraic semantics. We first present the algebraic laws for Verilog. Every program can be expressed as a guarded choice that can model the execution of a program. In order to investigate the parallel expansion laws, a sequence is introduced, indicating which instantaneous action is due to which exact parallel component. A head normal form is defined for each program by using a locality sequence. We provide a strategy for deriving the denotational semantics based on head normal form. Using this strategy, the denotational semantics for every program can be calculated. Program equivalence can also be explored by using the derived denotational semantics. A short version of this paper appeared in Proc. ICECCS 2006: 11th IEEE International Conference on Engineering of Complex Computer Systems [48]. This work is partially supported by the National Basic Research Program of China (No. 2005CB321904), the National High Technology Research and Development Program of China (No. 2007AA010302) and the National Natural Science Foundation of China (No. 90718004). Jonathan Bowen is a visiting professor at King’s College London and an emeritus professor at London South Bank University.     

One-sided forbidding grammars and selective substitution grammars

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a non-terminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form, while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, this paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, this paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.