A KAM theorem for space-multidimensional Hamiltonian PDEs

We describe a method of translating a Lambek grammar with one division into an equivalent context-free grammar whose size is bounded by a polynomial in the size of the original grammar. Earlier constructions by Buszkowski and Pentus lead to exponential growth of the grammar size.     

Normal form of derivations in the nonassociative and commutative lambek calculus with product

We show that derivations in the nonassociative and commutative Lambek calculus with product can be transformed to a normal form as it is the case with derivations in noncommutative calculi. As an application we obtain that the class of languages generated by categorial grammars based on the nonassociative and commutative Lambek calculus with product is included in the class of CF-languages. MSC: 68Q50, 03D15, 03B65.     

On Commutative and Nonassociative Syntactic Calculi and Categorial Grammars

Two axiomatizations of the nonassociative and commutative Lambek syntactic calculus are given and their equivalence is proved. The first axiomatization employs Permutation as the only structural rule, the second one, with no Permutation rule, employs only unidirectional types. It is also shown that in the case of the Ajdukiewicz calculus an analogous equivalence is valid only in the case of a restricted set of formulas. Unidirectional axiomatizations are employed in order to establish the generative power of categorial grammars based on the nonassociative and commutative Lambek calculus with product. Those grammars produce CF-languages of finite degree generated by CF-grammars closed with respect to permutations.     

Grammar functors and covers: From non-left-recursive to greibach normal form grammars

Attention is paid to structure preserving properties of transformations from a non-left-recursive context-free grammar to a Greibach normal form grammar. It is demonstrated that such a transformation cannot only be ambiguity preserving, but also both cover and functor relations between grammars or their associated syntax-categories can be obtained from such a transformation.     

Decidability and density in two-symbol grammar forms

It is proved that form equivalence is decidable for context-free grammar forms with only one nonterminal and one terminal symbol. However it also proved that there are “many” grammatical families generated by such forms: with some trivial exceptions, the families are dense in the sense that between any two families one can “squeeze” in a third one. The results obtained are applied also to L forms.     

A note on depth-first derivations

It is shown that the depth-first Szilard language associated with the depth-first derivations of a context-free grammar is ans-language.This work was supported by the Academy of Finland.     

Powerset Residuated Algebras and Generalized Lambek Calculus

We prove a representation theorem for (abstract) residuated algebras: each residuated algebra is isomorphically embeddable into a powerset residuated algebra. As a consequence, we obtain a completeness theorem for the Generalized Lambek Calculus. We use a Labelled Deductive System which generalizes the one used by Buszkowski [4] and Pankrat'ev [17] in completeness theorems for the Lambek Calculus.     

Lambek vs. Lambek: Functorial vector space semantics and string diagrams for Lambek calculus

The Distributional Compositional Categorical (DisCoCat) model is a mathematical framework that provides compositional semantics for meanings of natural language sentences. It consists of a computational procedure for constructing meanings of sentences, given their grammatical structure in terms of compositional type-logic, and given the empirically derived meanings of their words. For the particular case that the meaning of words is modelled within a distributional vector space model, its experimental predictions, derived from real large scale data, have outperformed other empirically validated methods that could build vectors for a full sentence. This success can be attributed to a conceptually motivated mathematical underpinning, something which the other methods lack, by integrating qualitative compositional type-logic and quantitative modelling of meaning within a category-theoretic mathematical framework. The type-logic used in the DisCoCat model is Lambek?s pregroup grammar. Pregroup types form a posetal compact closed category, which can be passed, in a functorial manner, on to the compact closed structure of vector spaces, linear maps and tensor product. The diagrammatic versions of the equational reasoning in compact closed categories can be interpreted as the flow of word meanings within sentences. Pregroups simplify Lambek?s previous type-logic, the Lambek calculus. The latter and its extensions have been extensively used to formalise and reason about various linguistic phenomena. Hence, the apparent reliance of the DisCoCat on pregroups has been seen as a shortcoming. This paper addresses this concern, by pointing out that one may as well realise a functorial passage from the original type-logic of Lambek, a monoidal bi-closed category, to vector spaces, or to any other model of meaning organised within a monoidal bi-closed category. The corresponding string diagram calculus, due to Baez and Stay, now depicts the flow of word meanings, and also reflects the structure of the parse trees of the Lambek calculus.     

Lambek calculus with a unit and one division

In this paper we present a substitution that reduces the derivability in the Lambek calculus with a unit and one division to the derivability in the Lambek calculus with one division permitting empty antecedents. Using this substitution, we establish the existence of an algorithm checking the derivability in the Lambek calculus with a unit and one division in polynomial time.     

Context-free grammars for triangular arrays

We consider context-free grammars of the form G = {f → fb1+b2+1ga1+a2, g → fb1 ga1+1},where ai and bi are integers sub ject to certain positivity conditions. Such a grammar G gives rise to triangular arrays {T(n, k)}0≤k≤n satisfying a three-term recurrence relation. Many combinatorial sequences can be generated in this way. Let Tn (x) =∑nk=0T(n, k)xk. Based on the differential operator with respect to G, we define a sequence of linear operators Pn such that Tn+1(x) = Pn(Tn(x)). Applying the characterization of real stability preserving linear operators on the multivariate polynomials due to Borcea and Br?ndén, we obtain a necessary and sufficient condition for the operator Pn to be real stability preserving for any n. As a consequence, we are led to a sufficient condition for the real-rootedness of the polynomials defined by certain triangular arrays, obtained by Wang and Yeh.Moreover, as special cases we obtain grammars that lead to identities involving the Whitney numbers and the Bessel numbers.     

Polarity of chordal graphs

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm.     

Context-free pairs of groups II - Cuts, tree sets, and random walks

This is a continuation of the study, begun by Ceccherini-Silberstein and Woess (2009) [5], of context-free pairs of groups and the related context-free graphs in the sense of Muller and Schupp (1985) [22]. The graphs under consideration are Schreier graphs of a subgroup of some finitely generated group, and context-freeness relates to a tree-like structure of those graphs. Instead of the cones of Muller and Schupp (1985) [22] (connected components resulting from deletion of finite balls with respect to the graph metric), a more general approach to context-free graphs is proposed via tree sets consisting of cuts of the graph, and associated structure trees. The existence of tree sets with certain "good" properties is studied. With a tree set, a natural context-free grammar is associated. These investigations of the structure of context free pairs, resp. graphs are then applied to study random walk asymptotics via complex analysis. In particular, a complete proof of the local limit theorem for return probabilities on any virtually free group is given, as well as on Schreier graphs of a finitely generated subgoup of a free group. This extends, respectively completes, the significant work of Lalley (1993, 2001) [18,20].     

Distributive residuated frames and generalized bunched implication algebras

We show that all extensions of the (non-associative) Gentzen system for distributive full Lambek calculus by simple structural rules have the cut elimination property. Also, extensions by such rules that do not increase complexity have the finite model property, hence many subvarieties of the variety of distributive residuated lattices have decidable equational theories. For some other extensions, we prove the finite embeddability property, which implies the decidability of the universal theory, and we show that our results also apply to generalized bunched implication algebras. Our analysis is conducted in the general setting of residuated frames.     

A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem

The multi-activity shift scheduling problem involves assigning a sequence of activities to a set of employees. In this paper, we consider the variant where the employees have different qualifications and each activity must be performed in a specified time window; i.e., we specify the earliest start period and the latest finish period. We propose a matheuristic in which Lagrangian relaxation is used to identify a subset of promising shifts, and a restricted set covering problem is solved to find a feasible solution. Each shift is represented by a context-free grammar. Computational tests are carried out on two sets of instances from the literature. For the first set, the matheuristic finds a solution with an optimality gap less than 0.01% for 70% of the instances and improves the best-known solution for 16% of them; for the second set, the matheuristic reaches the best-known solutions for 55% of the instances and finds better solutions for 37.5% of them.     

On permutative grammars generating context-free languages

A grammar is said to be permutative if it has permutation productions of the formAB BA in addition to context-free productions. Szilard languages and label languages are studied as examples of languages generable by permutative grammars. Particularly, sufficient conditions for a permutative grammar to generate a context-free language are studied.This work was supported by the Academy of Finland.     

Amalgams of finite inverse semigroups and deterministic context-free languages

Let S be the amalgamated free product of two finite inverse semigroups. We prove that the Schützenberger graph of an element of S with respect to a standard presentation of S is a context-free graph in the sense of Müller and Schupp (Theor. Comput. Sci. 37:51?C75, 1985), showing that the language L recognized by the Schützenberger automaton is context-free. Moreover we construct the grammar generating L proving that L is a deterministic context-free language and we use this fact for solving some algorithmic problems.     

A Labelled Deductive System for Relational Semantics of the Lambek Calculus

We present a labelled version of Lambek Calculus without unit, and we use it to prove a completeness theorem for Lambek Calculus with respect to some relational semantics.     

Some remarks on the Akivis algebras and the Pre-Lie algebras

In this paper, by using the Composition-Diamond lemma for non-associative algebras invented by A. I. Shirshov in 1962, we give Gröbner-Shirshov bases for free Pre-Lie algebras and the universal enveloping non-associative algebra of an Akivis algebra, respectively. As applications, we show I.P. Shestakov’s result that any Akivis algebra is linear and D. Segal’s result that the set of all good words in X** forms a linear basis of the free Pre-Lie algebra PLie(X) generated by the set X. For completeness, we give the details of the proof of Shirshov’s Composition-Diamond lemma for non-associative algebras.     

Monadic second-order model-checking on decomposable matroids

A notion of branch-width, which generalizes the one known for graphs, can be defined for matroids. We first give a proof of the polynomial time model-checking of monadic second-order formulas on representable matroids of bounded branch-width, by reduction to monadic second-order formulas on trees. This proof is much simpler than the one previously known. We also provide a link between our logical approach and a grammar that allows one to build matroids of bounded branch-width. Finally, we introduce a new class of non-necessarily representable matroids, described by a grammar and on which monadic second-order formulas can be checked in linear time.