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)

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)

Based on the computation mode introduced in [13], we deal with the time complexity of computations over arbitrary first-order structures.The main emphasis is on parameter-free computations. Some transfer results for solutions of P versus NP problems as well as relationships to quantifier elimination are discussed. By computation tree analysis using first-order formulas, it follows that P versus NP solutions and other results of structural complexity theory are invariant under elementary equivalence of structures.

Continuing the paper [7], in which the Blum-Shub-Smale approach to computability over the reals has been generalized to arbitrary algebraic structures, this paper deals with computability and recognizability over structures of infinite signature. It begins with discussing related properties of the linear and scalar real structures and of their discrete counterparts over the natural numbers. Then the existence of universal functions is shown to be equivalent to the effective encodability of the (...) underlying structure. Such structures even have universal functions satisfying the s-m-n theorem and related features. The real and discrete examples are discussed with respect to effective encodability. Megiddo structures and computational extensions of effectively encodable structures are encodable, too. As further variants of universality, universal functions with enumerable sets of program codes and such ones with constructible codes are investigated. Finally, the existence of m-complete sets is shown to be independent of the effective encodability of structures, and the linear and scalar structures are discussed once more, under this aspect. (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.

This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. (...) We show that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting. (shrink)

This paper studies the structure of semisimple rings using techniques of reverse mathematics, where a ring is left semisimple if the left regular module is a finite direct sum of simple submodules. The structure theorem of left semisimple rings, also called Wedderburn-Artin Theorem, is a famous theorem in noncommutative algebra, says that a ring is left semisimple if and only if it is isomorphic to a finite direct product of matrix rings over division rings. We provide a proof for (...) the theorem in $$\mathrm RCA_{0}$$, showing the structure theorem for computable semisimple rings. The decomposition of semisimple rings as finite direct products of matrix rings over division rings is unique. Based on an effective proof of the Jordan-Hölder Theorem for modules with composition series, we also provide an effective proof for the uniqueness of the matrix decomposition of semisimple rings in $$\mathrm RCA_{0}$$. (shrink)

We prove that all infinite Boolean rings have the property P ≠ NP according to the digital nondeterminism.

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)

In this paper we show that axiomatic extensions of H. Wansing’s connexive logic $$\textsf{C}$$ ( $$\textsf{C}^{\perp }$$ ) are algebraizable (in the sense of J.W. Blok and D. Pigozzi) with respect to sub-varieties of $$\textsf{C}$$ ( $$\textsf{C}^{\perp }$$ )-algebras. We develop the structure theory of $$\textsf{C}$$ ( $$\textsf{C}^{\perp }$$ )-algebras, and we prove their representability in terms of twist-like constructions over implicative lattices (Heyting algebras). As a consequence, we further clarify the relationship between the aforementioned classes. Finally, taking advantage (...) of the above machinery, we provide some preliminary remarks on the lattice of axiomatic extensions of $$\textsf{C}$$ ( $$\textsf{C}^{\perp }$$ ) as well as on some properties of their equivalent algebraic semantics. (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)

A novel algebraic structure of the genetic code is proposed. Here, the principal partitions of the genetic code table were obtained as equivalent classes of quotient spaces of the genetic code vector space over the Galois field of the four DNA bases. The new algebraic structure shows strong connections among algebraic relationships, codon assignment and physicochemical properties of amino acids. Moreover, a distance function defined between the codon binary representations in the vector space was demonstrated to (...) have a linear behavior respect to physical variables such as the mean of amino acids interaction energies in proteins. It was also noticed that the distance between wild type and mutant codons approach to smaller values in mutational variants of four genes, i.e., human phenylalanine hydroxylase, human β-globin, HIV-1 protease and HIV-1 reverse transcriptase. These results strongly suggest that deterministic rules must be involved in the genetic code origin. (shrink)

The topics approached in the 52 papers included in this book are: neutrosophic sets; neutrosophic logic; generalized neutrosophic set; neutrosophic rough set; multigranulation neutrosophic rough set (MNRS); neutrosophic cubic sets; triangular fuzzy neutrosophic sets (TFNSs); probabilistic single-valued (interval) neutrosophic hesitant fuzzy set; neutro-homomorphism; neutrosophic computation; quantum computation; neutrosophic association rule; data mining; big data; oracle Turing machines; recursive enumerability; oracle computation; interval number; dependent degree; possibility degree; power aggregation operators; multi-criteria group decision-making (MCGDM); expert set; soft sets; LA-semihypergroups; single valued (...) trapezoidal neutrosophic number; inclusion relation; Q-linguistic neutrosophic variable set; vector similarity measure; fundamental neutro-homomorphism theorem; neutro-isomorphism theorem; quasi neutrosophic triplet loop; quasi neutrosophic triplet group; BE-algebra; cloud model; Maclaurin symmetric mean; pseudo-BCI algebra; hesitant fuzzy set; photovoltaic plan; decision-making trial and evaluation laboratory (DEMATEL); Choquet integral; fuzzy measure; clustering algorithm; and many more. (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)

There has been increasing interest over the last few decades in the study of the effective content of Mathematics. One field whose effective content has been the subject of a large body of work, dating back at least to the early 1960s, is model theory. Several different notions of effectiveness of model-theoretic structures have been investigated. This communication is concerned withcomputablestructures, that is, structures with computable domains whose constants, functions, and relations are uniformly computable.In model theory, we (...) identify isomorphic structures. From the point of view of computable model theory, however, two isomorphic structures might be very different. For example, under the standard ordering of ω the success or relation is computable, but it is not hard to construct a computable linear ordering of type ω in which the successor relation is not computable. In fact, for every computably enumerable degree a, we can construct a computable linear ordering of type ω in which the successor relation has degree a. It is also possible to build two isomorphic computable groups, only one of which has a computable center, or two isomorphic Boolean algebras, only one of which has a computable set of atoms. Thus, for the purposes of computable model theory, studying structures up to isomorphism is not enough. (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)

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)

A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider its effective power over a cohesive set of natural numbers. A cohesive set is an infinite set of natural numbers that is indecomposable with respect to computably enumerable sets. It plays the role of an ultrafilter, and the elements of a cohesive power are the equivalence classes of certain partial computable functions determined by the (...) cohesive set. Thus, unlike many classical ultrapowers, a cohesive power is a countable structure. In this paper we focus on cohesive powers of graphs, equivalence structures, and computable structures with a single unary function satisfying various properties, which can also be viewed as directed graphs. For these computable structures, we investigate the isomorphism types of their cohesive powers, as well as the properties of cohesive powers when they are not isomorphic to the original structure. (shrink)

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in (...) terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers. (shrink)

We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.

The topics approached in this collection of papers are: neutrosophic sets; neutrosophic logic; generalized neutrosophic set; neutrosophic rough set; multigranulation neutrosophic rough set (MNRS); neutrosophic cubic sets; triangular fuzzy neutrosophic sets (TFNSs); probabilistic single-valued (interval) neutrosophic hesitant fuzzy set; neutro-homomorphism; neutrosophic computation; quantum computation; neutrosophic association rule; data mining; big data; oracle Turing machines; recursive enumerability; oracle computation; interval number; dependent degree; possibility degree; power aggregation operators; multi-criteria group decision-making (MCGDM); expert set; soft sets; LA-semihypergroups; single valued trapezoidal neutrosophic number; (...) inclusion relation; Q-linguistic neutrosophic variable set; vector similarity measure; fundamental neutro-homomorphism theorem; neutro-isomorphism theorem; quasi neutrosophic triplet loop; quasi neutrosophic triplet group; BE-algebra; cloud model; fuzzy measure; clustering algorithm; and many more. (shrink)

In this book the authors introduced the notions of soft neutrosophic algebraic structures. These soft neutrosophic algebraic structures are basically defined over the neutrosophic algebraic structures which means a parameterized collection of subsets of the neutrosophic algebraic structure. For instance, the existence of a soft neutrosophic group over a neutrosophic group or a soft neutrosophic semigroup over a neutrosophic semigroup, or a soft neutrosophic field over a neutrosophic field, or (...) a soft neutrosophic LA-semigroup over a neutrosophic LAsemigroup, or a soft neutosophic loop over a neutrosophic loop. It is interesting to note that these notions are defined over finite and infinite neutrosophic algebraic structures. These structures are even bigger than the classical algebraic structures. This book contains five chapters. Chapter one is about the introductory concepts. In chapter two the notions of soft neutrosophic group, soft neutrosophic bigroup and soft neutrosophic N-group are introduced and many fantastic properties are given with illustrative examples. (shrink)

We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type InfEx_\iso, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is InfEx_\iso-learnable if and only if the structures can be distinguished in terms of their \Sigma^2_inf-theories. We apply this characterization to familiar cases and we show the (...) following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable. (shrink)

In this book we define some new notions of soft neutrosophic algebraic structures over neutrosophic algebraic structures. We define some different soft neutrosophic algebraic structures but the main motivation is two-fold. Firstly the classes of soft neutrosophic group ring and soft neutrosophic semigroup ring defined in this book is basically the generalization of two classes of rings: neutrosophic group rings and neutrosophic semigroup rings. These soft neutrosophic group rings and soft neutrosophic semigroup rings (...) are defined over neutrosophic group rings and neutrosophic semigroup rings respectively. This is basically the collection of parameterized subneutrosophic group ring and subneutrosophic semigroup ring of a neutrosophic group ring and neutrosophic semigroup ring respectively. These soft neutrosophic algebraic structures are even bigger than the corresponding classical algebraic structures. It is interesting to see that it wider the area of research for the researcher of algebraic structures. (shrink)

We introduce Łukasiewicz-Moisil relation algebras, obtained by considering a relational dimension over Łukasiewicz-Moisil algebras. We prove some arithmetical properties, provide a characterization in terms of complex algebras, study the connection with relational Post algebras and characterize the simple structures and the matrix relation algebras.

There is a constructive method to define a structure of simple k-cyclic Post algebra of order p, L p,κ, on a given finite field F, and conversely. There exists an interpretation Ф₁ of the variety V generated by L p,κ into the variety V) generated by F and an interpretation Ф₂ of V) into V such that Ф₂Ф₁ = B for every B ϵ V and Ф₁₂ = R for every R ϵ V). In this paper we show how we (...) can solve an algebraic system of equations over an arbitrary cyclic Post algebra of order p, p prime, using the above interpretation, Gröbner bases and algorithms programmed in Maple. (shrink)

This paper is the concluding part of [1] and [2], and it investigates the inner structure of the lattice (MHA) of all varieties of monadic Heyting algebras. For every n , we introduce and investigate varieties of depth n and cluster n, and present two partitions of (MHA), into varieties of depth n, and into varieties of cluster n. We pay a special attention to the lower part of (MHA) and investigate finite and critical varieties of monadic Heyting algebras in (...) detail. In particular, we prove that there exist exactly thirteen critical varieties in (MHA) and that it is decidable whether a given variety of monadic Heyting algebras is finite or not. The representation of (MHA) is also given. All these provide us with a satisfactory insight into (MHA). Since (MHA) is dual to the lattice NExtMIPC of all normal extensions of the intuitionistic modal logic MIPC, we also obtain a clearer picture of the lattice structure of intuitionistic modal logics over MIPC. (shrink)

We show that true first-order arithmetic of the positive integers is interpretable over the real-algebraic structure of Scott's topological model for intuitionistic analysis. From this the undecidability of the structure follows.

We show that true first-order arithmetic is interpretable over the real-algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras. From this the undecidability of the structures follows. We also show that Scott's model is equivalent to true second-order arithmetic. In the appendix we argue that undecidability on the language of ordered rings follows from intuitionistically plausible properties of the real numbers.

We present algebraic semantics for the classical logic of proofs based on Boolean algebras. We also extend the language of the logic of proofs in order to have a Boolean structure on proof terms and equality predicate on terms. Moreover, the completeness theorem and certain generalizations of Stone’s representation theorem are obtained for all proposed algebras.

It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump. We also show that this result does not hold for the limit ordinal. Moreover, we prove that there is no countable structure with the degree spectrum for.

Let S be a signature of operations and relations definable in relation algebra, let R be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R or F for finite S-structures is undecidable, we reduce from a known undecidable problem—here we use the (...) tiling problem, the partial group embedding problem and the partial group finite embedding problem to prove undecidability of finite membership of R or F for various signatures S. It follows that the equational theory of R is undecidable whenever S includes the boolean operators and composition. We give an exposition of the reduction from the tiling problem and the reduction from the group embedding problem, and summarize what we know about the undecidability of finite membership of R and of F for different signatures S. (shrink)

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 Σ-algebra A to a computable metric partial Σ-algebra B must be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves the (...) class='Hi'>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. (shrink)

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)

There is currently much interest in bringing together the tradition of categorial grammar, and especially the Lambek calculus, with the recent paradigm of linear logic to which it has strong ties. One active research area is designing non-commutative versions of linear logic (Abrusci, 1995; Retoré, 1993) which can be sensitive to word order while retaining the hypothetical reasoning capabilities of standard (commutative) linear logic (Dalrymple et al., 1995). Some connections between the Lambek calculus and computations in groups have long been (...) known (van Benthem, 1986) but no serious attempt has been made to base a theory of linguistic processing solely on group structure. This paper presents such a model, and demonstrates the connection between linguistic processing and the classical algebraic notions of non-commutative free group, conjugacy, and group presentations. A grammar in this model, or G-grammar is a collection of lexical expressions which are products of logical forms, phonological forms, and inverses of those. Phrasal descriptions are obtained by forming products of lexical expressions and by cancelling contiguous elements which are inverses of each other. A G-grammar provides a symmetrical specification of the relation between a logical form and a phonological string that is neutral between parsing and generation modes. We show how the G-grammar can be oriented for each of the modes by reformulating the lexical expressions as rewriting rules adapted to parsing or generation, which then have strong decidability properties (inherent reversibility). We give examples showing the value of conjugacy for handling long-distance movement and quantifier scoping both in parsing and generation. The paper argues that by moving from the free monoid over a vocabulary V (standard in formal language theory) to the free group over V, deep affinities between linguistic phenomena and classical algebra come to the surface, and that the consequences of tapping the mathematical connections thus established can be considerable. (shrink)

In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the (...) other hand, we construct a pair of structures which is learnable but no computable learner can learn it. (shrink)

Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the correspondence between uniform AC0 and FO. We prove finite analogs of three classic results in arithmetical definability, namely that < and TIMES can first-order define PLUS, that < and DIVIDES can first-order define TIMES, and that < and COPRIME can first-order define TIMES. The first result sharpens the equivalence FO =FO (...) to FO = FO, answering a question raised by Barrington et al. about the Crane Beach Conjecture. Together with previous results on the Crane Beach Conjecture, our results imply that FO is strictly less expressive than FO = FO = FO. In more colorful language, one could say that, for parallel computation, multiplication is harder than addition. (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.

This paper studies algorithmic learning theory applied to algebraic structures. In previous papers, we have defined our framework, where a learner, given a family of structures, receives larger and larger pieces of an arbitrary copy of a structure in the family and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if there is a learner that eventually stabilizes to a correct conjecture. Here, we analyze (...) the number of mind changes that are needed to learn a given family K. We give a descriptive set-theoretic interpretation of such mind change complexity. We also study how bounding the Turing degree of learners affects the mind change complexity of a given family of algebraic structures. (shrink)

We define a formula φ in a first-order language L , to be an equation in a category of L -structures K if for any H in K , and set p = {φ;i ϵI, a i ϵ H} there is a finite set I 0 ⊂ I such that for any f : H → F in K , ▪. We say that an elementary first-order theory T which has the amalgamation property over substructures is equational if (...) every quantifier-free formula is equivalent in T to a boolean combination of equations in Mod, the category of models of T with embeddings for morphisms. Thus, we develop a theory of independence with respect to equations in general categories of structures, which is similar to the one introduced in stability but which, in our context, has an algebraic character. (shrink)

Structured argumentation systems, and their implementation, represent an important research subject in the area of Knowledge Representation and Reasoning. Structured argumentation advances over abstract argumentation frameworks by providing the internal construction of the arguments that are usually defined by a set of (strict and defeasible) rules. By considering the structure of arguments, it becomes possible to analyze reasons for and against a conclusion, and the warrant status of such a claim in the context of a knowledge base represents the (...) main output of a dialectical process. Computing such statuses is a costly process, and any update to the knowledge base could potentially have a huge impact if done naively. In this work, we investigate the case of updates consisting of both additions and removals of pieces of knowledge in the Defeasible Logic Programming (DeLP) framework, first analyzing the complexity of the problem and then identifying conditions under which we can avoid unnecessary computations—central to this is the development of structures (e.g. graphs) to keep track of which results can potentially be affected by a given update. We introduce a technique for the incremental computation of the warrant statuses of conclusions in DeLP knowledge bases that evolve due to the application of (sets of) updates. We present the results of a thorough experimental evaluation showing that our incremental approach yields significantly faster running times in practice, as well as overall fewer recomputations, even in the case of sets of updates performed simultaneously. (shrink)

This volume presents state-of-the-art papers on new topics related to neutrosophic theories, such as neutrosophic algebraic structures, neutrosophic triplet algebraic structures, neutrosophic extended triplet algebraic structures, neutrosophic algebraic hyperstructures, neutrosophic triplet algebraic hyperstructures, neutrosophic n-ary algebraic structures, neutrosophic n-ary algebraic hyperstructures, refined neutrosophic algebraic structures, refined neutrosophic algebraic hyperstructures, quadruple neutrosophic algebraic structures, refined quadruple neutrosophic algebraic structures, neutrosophic image processing, neutrosophic image (...) classification, neutrosophic computer vision, neutrosophic machine learning, neutrosophic artificial intelligence, neutrosophic data analytics, neutrosophic deep learning, and neutrosophic symmetry, as well as their applications in the real world. (shrink)

Based on the paper [4] we show that true second‐order arithmetic is interpretable over the real‐algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras.

This paper proposes to present a novel method of generating cryptographic dynamic substitution-boxes, which makes use of the combined effect of discrete hyperchaos mapping and algebraic group theory. Firstly, an improved 2D hyperchaotic map is proposed, which consists of better dynamical behaviour in terms of large Lyapunov exponents, excellent bifurcation, phase attractor, high entropy, and unpredictability. Secondly, a hyperchaotic key-dependent substitution-box generation process is designed, which is based on the bijectivity-preserving effect of multiplication with permutation matrix to obtain satisfactory (...) configuration of substitution-box matrix over the enormously large problem space of 256!. Lastly, the security strength of obtained S-box is further elevated through the action of proposed algebraic group structure. The standard set of performance parameters such as nonlinearity, strict avalanche criterion, bits independent criterion, differential uniformity, and linear approximation probability is quantified to assess the security and robustness of proposed S-box. The simulation and comparison results demonstrate the effectiveness of proposed method for the construction of cryptographically sound S-boxes. (shrink)

This paper was motivated by the following two questions which arise in the theory of complexity for computation over ordered rings in the now famous computational model introduced by Blum, Shub and Smale: 1. is the answer to the question P = ?NP the same in every real-closed field?2. if P ≠ NP for , does there exist a problem of which is NP but neither P nor NP-complete ?Some unclassical complexity classes arise naturally in the study of these (...) questions. They are still open, but we could obtain unconditional results of independent interest.Michaux introduced/const complexity classes in an effort to attack question . We show that , answering a question of his. Here A is the class of real problems which are algorithmic in bounded time. We also prove the stronger result: , where PAR stands for parallel polynomial time. In our terminology, we say that is A-saturated and PAR-saturated. We also prove, at the nonuniform level, the above results for every real-closed field. It is not known whether is P-saturated. In the case of the reals with addition and order we obtain P-saturation ). More generally, we show that an ordered -vector space is P-saturated at the nonuniform level ).We also study a stronger notion that we call P-stability. Blum, Cucker, Shub and Smale have shown that fields of characteristic 0 are P-stable. We show that the reals with addition and order are P-stable, but real-closed fields are not.Questions and and the/const complexity classes have some model theoretic flavor. This leads to the theory of complexity over “arbitrary” structures as introduced by Poizat. We give a summary of this theory with a special emphasis on the connections with model theory and we study/const complexity classes from this point of view. Note also that our proof of the PAR-saturation of shows that an o-minimal structure which admits quantifier elimination is A-saturated at the nonuniform level. (shrink)

We consider the complexity (in terms of the arithmetical hierarchy) of the various quantifier levels of the diagram of a computably presented metric structure. As the truth value of a sentence of continuous logic may be any real in [0, 1], we introduce two kinds of diagrams at each level: the closed diagram, which encapsulates weak inequalities of the form $$\phi ^\mathcal {M}\le r$$, and the open diagram, which encapsulates strict inequalities of the form $$\phi ^\mathcal {M}< r$$. We show (...) that the closed and open $$\Sigma _N$$ diagrams are $$\Pi ^0_{N+1}$$ and $$\Sigma ^0_N$$ respectively, and that the closed and open $$\Pi _N$$ diagrams are $$\Pi ^0_N$$ and $$\Sigma ^0_{N + 1}$$ respectively. We then introduce effective infinitary formulas of continuous logic and extend our results to the hyperarithmetical hierarchy. Finally, we demonstrate that our results are optimal. (shrink)

Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define (...) the same consequence relations for a given spi-logic. (shrink)

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)