Loading Events

The next meeting of the Algebra and Logic Seminar will be held online on November 24, 2023 (Friday) at 1:00 pm (UTC+2) with two talks.

At 1:00 pm (UTC+2) Dimitrinka Vladeva (IMI – BAS) will deliver a talk on

Catalan numbers and additively idempotent semirings

At 2:00 pm (UTC+2) Roussanka Loukanova (IMI – BAS) will deliver a talk on

Semantics of Propositional Attitudes in Type-Theory of Algorithms

Title: Catalan numbers and additively idempotent semirings

Abstract. The purpose of the present talk is to provide new applications of remarkable Catalan numbers. In Richard Stanley’s book Enumerative Combinatorics, Volume II (Cambridge University Press) there are many combinatorial objects that are counted by the Catalan numbers as well as applications in graph theory, Young diagrams, lattice theory, real matrices, real polynomials and so on. We show applications of Catalan numbers in some additively idempotent semirings which appeared in my results in 5 papers published between 2011 and 2023.

The set of nilpotent endomorphisms in the endomorphism semiring of a finite chain is a semiring of order (– 1)-th Catalan number and is an ideal in another semiring of order n-th Catalan number. The semiring of k th nilpotent endomorphisms, where 0 ≤ k ≤ n – 1 is of order a product of two Catalan numbers. By complex products of Catalan numbers we describe the roots of arbitrary idempotent of the endomorphism semiring of a finite chain.
In an additively idempotent semiring which is a generalization of the endomorphism semiring of a finite chain considered as a simplex we prove that the subsimplex of nilpotent elements is of order (n – 1)-th Catalan number and it is closed under derivations which are projections of the simplex to some simplices.
In the last paper, 2023, we prove that an additively idempotent semiring which is an S0-semialgebra, where S0 is a commutative additively idempotent semiring, and with a finite basis of a special type is isomorphic to a matrix semiring. As a consequence we obtain two different semirings of upper triangular matrices over the Boolean semiring, which are of order (n + 1)-th Catalan number.

Title: Semantics of Propositional Attitudes in Type-Theory of Algorithms

Abstract. Natural language (NL) is notorious for various kinds of ambiguities.  Among the most difficult ones, for computational handling of NL, are expressions with multiple occurrences of quantifiers, which contribute to quantifier scope ambiguities. Far more difficult for computational linguistics are NL expressions having occurrences of so-called attitude components designating knowledge, believes, statements, and similar semantic information.

Often, the syntactic complement of an attitude lexeme is a sentential expression. The sentential complement may have subexpressions that designate semantic information belonging to varying scopes.  Depending on context, some components can be semantic parts of the attitudinal information, which is in the scope of the propositional attitude, or external to it.

The first formal representation of NL attitudes was by Montague, 1973, along with the quantifier scope ambiguities, by the notions of extension and intension, and using extra-syntactic disambiguation of NL expressions. That approach, while unsatisfactory in important aspects, was adopted and adapted by some variants of Montague grammars, for specific purposes. The problem has been largely open, due to its purely semantic nature and computational difficulties, without direct syntactic appearance.

The semantic phenomena of attitudes include statements in natural language, including in the domains of mathematical texts and proofs.

In this presentation of a recent paper, I extend the type-theory of algorithms, to cover algorithmic semantics of some of the major attitude expressions and their semantic underspecification. I provide reduction calculus for deriving semantic specifications in contexts.


Link to the Zoom room:


Algebra and Logic Department, IMI – BAS
============================== =====================

Share This Story, Choose Your Platform!

Go to Top