Though some influentially critical objections have been raised during the ‘classical’ pre-computational simulation philosophy of science tradition, suggesting a more nuanced methodological category for experiments, it safe to say such critical objections have greatly proliferated in philosophical studies dedicated to the role played by computational simulations in science. For instance, Eric Winsberg suggests that computer simulations are methodologically unique in the development of a theory’s models suggesting new epistemic notions of application. This is also echoed in Jeffrey Ramsey’s notions of (...) “transformation reduction,”—i.e., a notion of reduction of a more highly constructive variety. Computer simulations create a broadly continuous arena spanned by normative and descriptive aspects of theory-articulation, as entailed by the notion of transformation reductions occupying a continuous region demarcated by Ernest Nagel’s logical-explanatory “domain-combining reduction” on the one hand, and Thomas Nickels’ heuristic “domain-preserving reduction,” on the other. I extend Winsberg’s and Ramsey’s points here, by arguing that in the field of computational fluid dynamics as well as in other branches of applied physics, the computer plays a constitutively experimental role—supplanting in many cases the more traditional experimental methods such as flow-visualization, etc. In this case, however CFD algorithms act as substitutes, not supplements when it comes to experimental practices. I bring up the constructive example involving the Clifford-Algebraic algorithms for modeling singular phenomena in CFD by Gerik Scheuermann and Steven Mann & Alyn Rockwood who demonstrate that their algorithms offer greater descriptive and explanatory scope than the standard Navier-Stokes approaches. The mathematical distinction between Navier-Stokes-based and Clifford-Algebraic based CFD has essentially to do with the regularization features exhibited to a far greater extent by the latter, than the former. Hence, CACFD indicate that the utilization of computational techniques can be based on principled reasons, as opposed to merely practical. CACFD hence exhibit a new generative role in the field of fluid mechanics, by offering categories of experimental evidence that are optimally descriptive and explanatory—i.e., pace Batterman can be both ontologically and epistemically fundamental. (shrink)

Computational implementations are special relations between what is computed and what computes it. Though the word “isomorphism” appears in philosophical discussions about the nature of implementations, it is used only metaphorically. Here we discuss computation in the precise language of abstract algebra. The capability of emulating computers is the defining property of computers. Such a chain of emulation is ultimately grounded in an algebraic object, a full transformation semigroup. Mathematically, emulation is defined by structure preserving maps (morphisms) between semigroups. (...) These are systematic, very special relationships, crucial for defining implementation. In contrast, interpretations are general functions with no morphic properties. They can be used to derive semantic content from computations. Hierarchical structure imposed on a computational structure plays a similar semantic role. Beyond bringing precision into the investigation, the algebraic approach also sheds light on the interplay between time and computation. (shrink)

In this paper we investigate a categorical equivalence between square root qMV-algehras (a variety of algebras arising from quantum computation) and a category of preordered semigroups.

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity (...) in a BSS-like manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)

In earlier work we have described how computer algebra may be used to derive composite rate laws for complete systems of equations, using the mathematical technique of Gröbner Bases (Bennett, Davenport and Sauro, 1988). Such composite rate laws may then be fitted to experimental data to yield estimates of kinetic parameters.Recently we have been investigating the practical application of this methodology to the estimation of kinetic parameters for the closed two enzyme system of aspartate aminotransferase (AAT) and malate dehydrogenase (MDH) (...) (Fisher 1990a; Fisher 1990b; Bennett and Fisher, 1990). (shrink)

This paper shows how the notion of randomness defines, in a natural way, an algebra. It turns out that the algebra is computably enumerable and finitely generated. The paper investigates algebraic and effective properties of this algebra.

We initiate the study of computable presentations of real and complex C*-algebras under the program of effective metric structure theory. With the group situation as a model, we develop corresponding notions of recursive presentations and word problems for C*-algebras, and show some analogous results hold in this setting. Famously, every finitely generated group with a computable presentation is computably categorical, but we provide a counterexample in the case of C*-algebras. On the other hand, we show every finite-dimensional C*-algebra is computably (...) categorical. (shrink)

This volume contains the proceedings of three special sessions: Algebra and Computer Science, held during the Joint AMS-EMS-SPM meeting in Porto, Portugal, June 10–13, 2015; Groups, Algorithms, and Cryptography, held during the Joint Mathematics Meeting in San Antonio, TX, January 10–13, 2015; and Applications of Algebra to Cryptography, held during the Joint AMS-Israel Mathematical Union meeting in Tel-Aviv, Israel, June 16–19, 2014. Papers contained in this volume address a wide range of topics, from theoretical aspects of algebra, namely group theory, (...) universal algebra and related areas, to applications in several different areas of computer science. From the computational side, the book aims to reflect the rapidly emerging area of algorithmic problems in algebra, their computational complexity and applications, including information security, constraint satisfaction problems, and decision theory. The book gives special attention to recent advances in quantum computing that highlight the need for a variety of new intractability assumptions and have resulted in a new area called group-based cryptography. (shrink)

We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d' = θ", but that not all such fields are 0'-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many‐sorted metric partial algebra, thus extending the axiomatisation given by Pour‐El and Richards in [9] for Banach spaces. We show that every Banach‐Mazur computable partial function from an effectively separable computable metric partial Σ‐algebraAto a computable metric partial Σ‐algebraBmust be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves the computability of a computably (...) enumerable dense set must be computable. Finally, as an application of these results we give an alternative proof of the first main theorem for Banach spaces first proved by Pour‐El and Richards. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the basic algebraic properties of this system by introducing the notion of Shi-Aharonov quantum computational structure. We show that the quotient of this structure is isomorphic to a structure based on a particular set of complex numbers (the closed disc with center \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{1}{2},\frac{1}{2})$\end{document} and radius (...) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{1}{2}$\end{document} ). (shrink)

We introduce a generalization of MV algebras motivated by the investigations into the structure of quantum logical gates. After laying down the foundations of the structure theory for such quasi-MV algebras, we show that every quasi-MV algebra is embeddable into the direct product of an MV algebra and a “flat” quasi-MV algebra, and prove a completeness result w.r.t. a standard quasi-MV algebra over the complex numbers.

We obtain an algorithm to compute finite coproducts of finitely generated Gödel algebras, i.e. Heyting algebras satisfying the prelinearity axiom =1. We achieve this result using ordered partitions of finite sets as a key tool to investigate the category opposite to finitely generated Gödel algebras . We give two applications of our main result. We prove that finitely presented Gödel algebras have free products with amalgamation; and we easily obtain a recursive formula for the cardinality of the free Gödel algebra (...) over a finite number of generators first established by A. Horn. (shrink)

We present the history of the conference Applications of Algebra in Logic and Computer Science, whose twenty-third edition will be held in March, 2019. At the end we outline some plans for the future.

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. (...) Our main computability concepts are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

In this paper we investigate computable isomorphisms of Boolean algebras with operators (BAOs). We prove that there are examples of polymodal Boolean algebras with finitely many computable isomorphism types. We provide an example of a polymodal BAO such that it has exactly one computable isomorphism type but whose expansions by a constant have more than one computable isomorphism type. We also prove a general result showing that BAOs are complete with respect to the degree spectra of structures, computable dimensions, expansions (...) by constants, and the degree spectra of relations. (shrink)

We prove a number of elementary facts about computability in partial combinatory algebras. We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

The paper studies Heyting algebras within the framework of computable structure theory. We prove that the class _K_ containing all Heyting algebras with distinguished atoms and coatoms is complete in the sense of the work of Hirschfeldt et al. (Ann Pure Appl Logic 115(1-3):71-113, 2002). This shows that the class _K_ is rich from the computability-theoretic point of view: for example, every possible degree spectrum can be realized by a countable structure from _K_. In addition, there is no simple (...) syntactic characterization of computably categorical members of _K_ (i.e., structures from _K_ possessing a unique computable copy, up to computable isomorphisms). (shrink)

In this paper, we present a computational algebraic representation of Hindi syntax. This paper is the first attempt to establish the representation of various facets of Hindi syntax into algebra, including dual nominative/ergative behavior, a syntacto-semantic case system and complex agreement rules between the noun and verb phrase. Using the pregroup analysis framework, we show how we represent morphological type reduction for morphological behavior of lexical markers, the representation of causative constructions which are morphologically affixed, as well as of (...) light verb constructions which form the verb by joint predication. We present examples adapted from the Hindi Dependency Treebank to show the pregroup analysis of Hindi sentences. (shrink)

Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in (...) the given class in a way that is effective enough to preserve the property in which we are interested. In this paper, we show how to transfer a number of computability-theoretic properties from directed graphs to structures in the following classes: symmetric, irreflexive graphs; partial orderings; lattices; rings ; integral domains of arbitrary characteristic; commutative semigroups; and 2-step nilpotent groups. This allows us to show that several theorems about degree spectra of relations on computable structures, nonpreservation of computable categoricity, and degree spectra of structures remain true when we restrict our attention to structures in any of the classes on this list. The codings we present are general enough to be viewed as establishing that the theories mentioned above are computably complete in the sense that, for a wide range of computability-theoretic nonstructure type properties, if there are any examples of structures with such properties then there are such examples that are models of each of these theories. (shrink)

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...) will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

ABSTRACT In this paper we present a new semantic approach for propositional linear temporal logic with discrete time, strongly based in the well-order of IN (the set of natural numbers). We consider temporal connectives which express precedence, posteriority and simultaneity, and they provide a family of expressively complete temporal logics. The selection of the new semantics and connectives used in this work was principally to obtain a suitable executable temporal logic, which can be used for the specification and control of (...) process behaviour in discrete time in a similar way to thai presented by D. Gabbay in [GAB 89], Our new approach has two advantages: firstly, the connectives are defined intuitively so that they have interpretations which relate to properties of interest in real systems; secondly, it provides a new semantics that facilitates simpler proofs of many valid formulas and metatheorems. To confirm this second advantage, we use our semantics to give a formal proof of the Separation Theorem for one of these logics (specifically LN3). The great interest of this Separation Theorem for the executable temporal logic is emphasised by D. Gabbay in [GAB 89], [GAB 88]. (shrink)

Through our work to examine mathematical and computational learning in authentic and convivial contexts that requires creativity, imagination, reasoning, and discourse, we have theorized an experiential learning cycle that attends to the development of voice, agency, and identity needed in young people for an earned insurgency—the right to demand change. Our work underscores how the current situation that many students face in classrooms amounts to a type of cognitive segregation that denies these students access to authentic and empowering intellectual agency. (...) By facilitating a process whereby students, using their own creative and imaginative means, intentionally develop a type of ownership over the exploration and application of the mathematical concepts they are being taught, we help students move from simple surface level, syntactic understandings, to deeper semantic learning that is more personally significant and meaningful. (shrink)

We show that there is a structure of countably infinite signature with $P = N_{2}P$ and a structure of finite signature with $P = N_{1}P$ and $N_{1}P \neq N_{2}P$ . We give a further example of a structure of finite signature with $P \neq N_{1}P$ and $N_{1}P \neq N_{2}P$ . Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for (...) some finite ℒ the class of ℒ-structures with $P = N_{1}P$ is not closed under ultraproducts and obtain as corollaries that this class is not $\delta$ -elementary and that the class of ᵍ-structures with $P \neq N_{1}P$ is not elementary. Finally we prove that for all f dominating all polynomials there is a structure of finite signature with the following properties: $P \neq N_{1}P$ . $N_{1}P \neq N_{2}P$ , the levels $N_{2}TIME(n^{i})$ of $N_{2}P$ and the levels $N_{1}TIME(n^{i})$ of $N_{1}P$ are different for different i, indeed $DTIME(n^{i'}) \nsubseteq N_{2}TIME(n^{i})$ if $i' \textgreater i$ ; $DTIME(f) \nsubseteq N_{2}P$ , and $N_{2}P \nsubseteq DEC$ . DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of $N_{2}P$ is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts. (shrink)

A complete classification of simple function germs with respect to Lipschitz equivalence over the field of complex numbers ℂ was given by Nguyen et al. The aim of this article is to implement a classifier in terms of easy computable invariants to compute the type of the Lipschitz simple function germs without computing the normal form in the computer algebra system Singular.

This book celebrates the work of Don Pigozzi on the occasion of his 80th birthday. In addition to articles written by leading specialists and his disciples, it presents Pigozzi’s scientific output and discusses his impact on the development of science. The book both catalogues his works and offers an extensive profile of Pigozzi as a person, sketching the most important events, not only related to his scientific activity, but also from his personal life. It reflects Pigozzi's contribution to the rise (...) and development of areas such as abstract algebraic logic, universal algebra and computer science, and introduces new scientific results. Some of the papers also present chronologically ordered facts relating to the development of the disciplines he contributed to, especially abstract algebraic logic. The book offers valuable source material for historians of science, especially those interested in history of mathematics and logic. (shrink)

It has become a fact that fluency and competency in utilizing the advancement of technology, specifically the computer and the internet is one way that could help in facilitating learning in mathematics. This study investigated the effects of Dynamic Geometry Software (DGS) and Computer Algebra Systems (CAS) in teaching Mathematics. This was conducted in Zamboanga del Sur National High School (ZSNHS) during the third grading period of the school year 2015-2016. The study compared the achievement and attitude towards Mathematics between (...) those students taught with DGS and CAS and those students who were taught without DGS and CAS. A quasi-experimental pretest-posttest control group design was used with two groups which was matched according to their mathematical level. An achievement test was developed and administered to assess the students’ achievement in Mathematics. Aiken’s attitude scale was also used to assess the students’ attitude towards Mathematics. The data were treated with One-Way Analysis of Covariance (ANCOVA) and t-test at 0.05 level of significance. The study revealed a significant difference between the mathematics achievement between students taught with DGS and CAS and those who were taught without it. The integration of DGS and CAS in Mathematics lessons leads to better academic achievement result compared with that of the conventional method of teaching. Moreover, there was no significant difference on the attitude level of the students between the two groups. (shrink)

This unique textbook states and proves all the major theorems of many-valued propositional logic and provides the reader with the most recent developments and trends, including applications to adaptive error-correcting binary search. The book is suitable for self-study, making the basic tools of many-valued logic accessible to students and scientists with a basic mathematical knowledge who are interested in the mathematical treatment of uncertain information. Stressing the interplay between algebra and logic, the book contains material never before published, such as (...) a simple proof of the completeness theorem and of the equivalence between Chang's MV algebras and Abelian lattice-ordered groups with unit - a necessary prerequisite for the incorporation of a genuine addition operation into fuzzy logic. Readers interested in fuzzy control are provided with a rich deductive system in which one can define fuzzy partitions, just as Boolean partitions can be defined and computed in classical logic. Detailed bibliographic remarks at the end of each chapter and an extensive bibliography lead the reader on to further specialised topics. (shrink)

In this paper the structure of pretemporal algebra is used to study some aspects of temporal algebras and modal algebras. The paper contains a computational approach to finite temporal algebras and a general splitting theorem for finite temporal algebras.

We introduce new algebraic and topological semantics for inquisitive logic. The algebraic semantics is based on special Heyting algebras, which we call inquisitive algebras, with propositional valuations ranging over only the ¬¬-fixpoints of the algebra. We show how inquisitive algebras arise from Boolean algebras: for a given Boolean algebra B, we define its inquisitive extension H(B) and prove that H(B) is the unique inquisitive algebra having B as its algebra of ¬¬-fixpoints. We also show that inquisitive algebras determine (...) Medvedev’s logic of finite problems. In addition to the algebraic characterization of H(B), we give a topological characterization of H(B) in terms of the recently introduced choice-free duality for Boolean algebras using so-called upper Vietoris spaces (UV-spaces). In particular, while a Boolean algebra B is realized as the Boolean algebra of compact regular open elements of a UV-space dual to B, we show that H(B) is realized as the algebra of compact open elements of this space. This connection yields a new topological semantics for inquisitive logic. (shrink)

This volume presents the state of the art in the algebraic investigation into substructural logics. It features papers from the workshop AsubL (Algebra & Substructural Logics - Take 6). Held at the University of Cagliari, Italy, this event is part of the framework of the Horizon 2020 Project SYSMICS: SYntax meets Semantics: Methods, Interactions, and Connections in Substructural logics. -/- Substructural logics are usually formulated as Gentzen systems that lack one or more structural rules. They have been intensively studied (...) over the past two decades by logicians of various persuasions. These researchers include mathematicians, philosophers, linguists, and computer scientists. Substructural logics are applicable to the mathematical investigation of such processes as resource-conscious reasoning, approximate reasoning, type-theoretical grammar, and other focal notions in computer science. They also apply to epistemology, economics, and linguistics. The recourse to algebraic methods -- or, better, the fecund interplay of algebra and proof theory -- has proved useful in providing a unifying framework for these investigations. The AsubL series of conferences, in particular, has played an important role in these developments. -/- This collection will appeal to students and researchers with an interest in substructural logics, abstract algebraic logic, residuated lattices, proof theory, universal algebra, and logical semantics. (shrink)

Results of R. Miller in 2009 proved several theorems about algebraic fields and computable categoricity. Also in 2009, A. Frolov, I. Kalimullin, and R. Miller proved some results about the degree spectrum of an algebraic field when viewed as a subfield of its algebraic closure. Here, we show that the same computable categoricity results also hold for finite-branching trees under the predecessor function and for connected, finite-valence, pointed graphs, and we show that the degree spectrum results do (...) not hold for these trees and graphs. We also offer an explanation for why the degree spectrum results distinguish these classes of structures: although all three structures are algebraic structures, the fields are what we call effectively algebraic. (shrink)