Search

Mathematical documents written in LaTeX often contain ambiguities. We can resolve some of them via semantic markup using, e.g., sTeX, which also has other potential benefits, such as interoperability with computer algebra systems, proof systems, and increased accessibility. However, semantic markup is more involved than "regular" typesetting and presents a challenge for authors of mathematical documents. We aim to smooth out the transition from plain LaTeX to semantic markup by developing semi-automatic tools for authors. In this paper we present an approach to semantic markup of formulas by (semi-)automatically generating grammars from existing sTeX macro definitions and parsing mathematical formulas with them. We also present a GUI-based tool for the disambiguation of parse results and showcase its functionality and potential using a grammar for parsing untyped $\lambda$-terms., Comment: Submitted to the CICM 2024 conference, due to be published in Volume 14960 of Springer's Lecture Notes in Computer Science

The lambda-cube is a famous pure type system (PTS) cube of eight powerful explicit type systems that include the simple, polymorphic and dependent type theories. The lambda-cube only types Strongly Normalising (SN) terms but not all of them. It is well known that even the most powerful system of the lambda-cube can only type the same pure untyped lambda-terms that are typable by the higher-order polymorphic implicitly typed lambda-calculus Fomega, and that there is an untyped {\lambda}-term U' that is SN but is not typable in Fomega or the lambda-cube. Hence, neither system can type all the SN terms it expresses. In this paper, we present the f-cube, an extension of the lambda-cube with finite-set declarations (FSDs) like y\in{C1,...,Cn} : B which means that y is of type B and can only be one of C1,..., Cn. The novelty of our FSDs is that they allow to represent intersection types as Pi-types. We show how to translate and type the term U' in the f-cube using an encoding of intersection types based on FSDs. Notably, our translation works without needing anything like the usual troublesome intersection-introduction rule that proves a pure untyped lambda-term M has an intersection of k types using k independent sub-derivations. As such, our approach is useful for language implementers who want the power of intersection types without the pain of the intersection-introduction rule., Comment: To appear in Wollic 2024

This paper looks at how ancient mathematicians (and especially the Pythagorean school) were faced by problems/paradoxes associated with the infinite which led them to juggle two systems of numbers: the discrete whole/rationals which were handled arithmetically and the continuous magnitude quantities which were handled geometrically. We look at how approximations and mixed numbers (whole numbers with fractions) helped develop the arithmetization of geometry and the development of mathematical analysis and real numbers., Comment: To appear in 2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)

Substitution plays a prominent role in the foundation and implementation of mathematics and computation. In the lambda calculus, we cannot define alpha congruence without a form of substitution but for substitution and reduction to work, we need to assume a form of alpha congruence (e.g., when we take lambda terms modulo bound variables). Students on a lambda calculus course usually find this confusing. The elegant writings and research of the Curry school have settled this problem very well. This article is an ode to the contributions of the Curry school (especially the excellent book of Hindley and Seldin) on the subject of alpha congruence and substitution.

Much mathematical writing exists that is, explicitly or implicitly, based on set theory, often Zermelo-Fraenkel set theory (ZF) or one of its variants. In ZF, the domain of discourse contains only sets, and hence every mathematical object must be a set. Consequently, in ZF, with the usual encoding of an ordered pair ${\langle a, b\rangle}$, formulas like ${\{a\} \in \langle a, b \rangle}$ have truth values, and operations like ${\mathcal P (\langle a, b\rangle)}$ have results that are sets. Such 'accidental theorems' do not match how people think about the mathematics and also cause practical difficulties when using set theory in machine-assisted theorem proving. In contrast, in a number of proof assistants, mathematical objects and concepts can be built of type-theoretic stuff so that many mathematical objects can be, in essence, terms of an extended typed ${\lambda}$-calculus. However, dilemmas and frustration arise when formalizing mathematics in type theory. Motivated by problems of formalizing mathematics with (1) purely set-theoretic and (2) type-theoretic approaches, we explore an option with much of the flexibility of set theory and some of the useful features of type theory. We present ZFP: a modification of ZF that has ordered pairs as primitive, non-set objects. ZFP has a more natural and abstract axiomatic definition of ordered pairs free of any notion of representation. This paper presents axioms for ZFP, and a proof in ZF (machine-checked in Isabelle/ZF) of the existence of a model for ZFP, which implies that ZFP is consistent if ZF is. We discuss the approach used to add this abstraction barrier to ZF.

Global gender disparity in science is an unsolved problem. Predicting gender has an important role in analysing the gender gap through online data. We study this problem within the UK, Malaysia and China. We enhance the accuracy of an existing gender prediction tools of names that can predict the sex of Chinese characters and English characters simultaneously and with more precision. During our research, we found that there is no free gender forecasting tool to predict an arbitrary number of names. We addressed this shortcoming by providing a tool that can predict an arbitrary number of names with free requests. We demonstrate our tool through a number of experimental results. We show that this tool is better than other gender prediction tools of names for analysing social problems with big data. In our approach, lists of data can be dynamically processed and the results of the data can be displayed with a dynamic graph. We present experiments of using this tool to analyse the gender disparity in computer science in the UK, Malaysia and China.

Following the introduction of BNF notation by Backus for the Algol 60 report and subsequent notational variants, a metalanguage involving formal "grammars" has developed for discussing structured objects in Computer Science and Mathematical Logic. We refer to this offspring of BNF as Math-BNF or MBNF, to the original BNF and its notational variants just as BNF, and to aspects common to both as BNF-style. What all BNF-style notations share is the use of production rules roughly of this form: $$\bullet \mathrel{::=} \circ_1 \mid \cdots \mid \circ_n $$ Normally, such a rule says "every instance of $\circ_i$ for $i \in \{1, \ldots, n\}$ is also an in stance of $\bullet$". MBNF is distinct from BNF in the entities and operations it allows. Instead of strings, MBNF builds arrangements of symbols that we call math-text. Sometimes "syntax" is defined by interleaving MBNF production rules and other mathematical definitions that can contain chunks of math-text. There is no clear definition of MBNF. Readers do not have a document which tells them how MBNF is to be read and must learn MBNF through a process of cultural initiation. To the extent that MBNF is defined, it is largely through examples scattered throughout the literature and which require readers to guess the mathematical structures underpinning them. This paper gives MBNF examples illustrating some of the differences between MBNF and BNF. We propose a definition of syntactic math text (SMT) which handles many (but far from all) uses of math-text and MBNF in the wild. We aim to balance the goal of being accessible and not requiring too much prerequisite knowledge with the conflicting goal of providing a rich mathematical structure that already supports many uses and has possibilities to be extended to support more challenging cases.

Symbolic computation is the science of computing with symbolic objects (terms, formulae, programs, algebraic objects, geometrical objects, etc). Powerful symbolic algorithms have been developed during the past decades and have played an influential role in theorem proving, automated reasoning, software verification, model checking, rewriting, formalisation of mathematics, network security, Groebner bases, characteristic sets, etc. The international Symposium on "Symbolic Computation in Software Science" is the fourth in the SCSS workshop series. SCSS 2008 and 2010 took place at the Research Institute for Symbolic Computation (RISC), Hagenberg, Austria, and, SCSS 2009 took place in Gammarth, Tunisia. These symposium grew out of internal workshops that bring together researchers from: a) SCORE (Symbolic Computation Research Group) at the University of Tsukuba, Japan, b) Theorema Group at the Research Institute for Symbolic Computation, Johannes Kepler University Linz, Austria, c) SSFG (Software Science Foundation Group) at Kyoto University, Japan, and d) Sup'Com (Higher School of Communication of Tunis) at the University of Carthage, Tunisia.

The lambda-calculus with de Bruijn indices assembles each alpha-class of lambda-terms in a unique term, using indices instead of variable names. Intersection types provide finitary type polymorphism and can characterise normalisable lambda-terms through the property that a term is normalisable if and only if it is typeable. To be closer to computations and to simplify the formalisation of the atomic operations involved in beta-contractions, several calculi of explicit substitution were developed mostly with de Bruijn indices. Versions of explicit substitutions calculi without types and with simple type systems are well investigated in contrast to versions with more elaborate type systems such as intersection types. In previous work, we introduced a de Bruijn version of the lambda-calculus with an intersection type system and proved that it preserves subject reduction, a basic property of type systems. In this paper a version with de Bruijn indices of an intersection type system originally introduced to characterise principal typings for beta-normal forms is presented. We present the characterisation in this new system and the corresponding versions for the type inference and the reconstruction of normal forms from principal typings algorithms. We briefly discuss the failure of the subject reduction property and some possible solutions for it.

Expansion was invented at the end of the 1970s for calculating principal typings for $\lambda$-terms in type systems with intersection types. Expansion variables (E-variables) were invented at the end of the 1990s to simplify and help mechanise expansion. Recently, E-variables have been further simplified and generalised to also allow calculating type operators other than just intersection. There has been much work on denotational semantics for type systems with intersection types, but none whatsoever before now on type systems with E-variables. Building a semantics for E-variables turns out to be challenging. To simplify the problem, we consider only E-variables, and not the corresponding operation of expansion. We develop a realisability semantics where each use of an E-variable in a type corresponds to an independent degree at which evaluation occurs in the $\lambda$-term that is assigned the type. In the $\lambda$-term being evaluated, the only interaction possible between portions at different degrees is that higher degree portions can be passed around but never applied to lower degree portions. We apply this semantics to two intersection type systems. We show these systems are sound, that completeness does not hold for the first system, and completeness holds for the second system when only one E-variable is allowed (although it can be used many times and nested). As far as we know, this is the first study of a denotational semantics of intersection type systems with E-variables (using realisability or any other approach).

Expansion was introduced at the end of the 1970s for calculating principal typings for $\lambda$-terms in intersection type systems. Expansion variables (E-variables) were introduced at the end of the 1990s to simplify and help mechanise expansion. Recently, E-variables have been further simplified and generalised to also allow calculating other type operators than just intersection. There has been much work on semantics for intersection type systems, but only one such work on intersection type systems with E-variables. That work established that building a semantics for E-variables is very challenging. Because it is unclear how to devise a space of meanings for E-variables, that work developed instead a space of meanings for types that is hierarchical in the sense of having many degrees (denoted by indexes). However, although the indexed calculus helped identify the serious problems of giving a semantics for expansion variables, the sound realisability semantics was only complete when one single E-variable is used and furthermore, the universal type $\omega$ was not allowed. In this paper, we are able to overcome these challenges. We develop a realisability semantics where we allow an arbitrary (possibly infinite) number of expansion variables and where $\omega$ is present. We show the soundness and completeness of our proposed semantics., Comment: 5th International Colloquium on Theoretical Aspects of Computing, ICTAC 2008, 1-3 September 2008, Istanbul : Turquie (2008)

In this paper we consider a type system with a universal type $\omega$ where any term (whether open or closed, $\beta$-normalising or not) has type $\omega$. We provide this type system with a realisability semantics where an atomic type is interpreted as the set of $\lambda$-terms saturated by a certain relation. The variation of the saturation relation gives a number of interpretations to each type. We show the soundness and completeness of our semantics and that for different notions of saturation (based on weak head reduction and normal $\beta$-reduction) we obtain the same interpretation for types. Since the presence of $\omega$ prevents typability and realisability from coinciding and creates extra difficulties in characterizing the interpretation of a type, we define a class ${\mathbb U}^+$ of the so-called positive types (where $\omega$ can only occur at specific positions). We show that if a term inhabits a positive type, then this term is $\beta$-normalisable and reduces to a closed term. In other words, positive types can be used to represent abstract data types. The completeness theorem for ${\mathbb U}^+$ becomes interesting indeed since it establishes a perfect equivalence between typable terms and terms that inhabit a type. In other words, typability and realisability coincide on ${\mathbb U}^+$. We give a number of examples to explain the intuition behind the definition of ${\mathbb U}^+$ and to show that this class cannot be extended while keeping its desired properties.