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 the notions of a mutually algebraic structures and theories and prove many equivalents. A theory $T$ is mutually algebraic if and only if it is weakly minimal and trivial if and only if no model $M$ of $T$ has an expansion $(M,A)$ by a unary predicate with the finite cover property. We show that every structure has a maximal mutually algebraic reduct, and give a strong structure theorem for the class of elementary extensions of (...) a fixed mutually algebraic structure. (shrink)

It is well-known that intuitionistic logics can be formalized by means of Heyting algebras, i.e. relatively pseudocomplemented semilattices. Within such algebras the logical connectives implication and conjunction are formalized as the relative pseudocomplement and the semilattice operation meet, respectively. If the Heyting algebra has a bottom element |$0$|⁠, then the relative pseudocomplement with respect to |$0$| is called the pseudocomplement and it is considered as the connective negation in this logic. Our idea is to consider an arbitrary meet-semilattice with |$0$| (...) satisfying only the Ascending Chain Condition (these assumptions are trivially satisfied in finite meet-semilattices) and introduce the operators formalizing the connectives negation |$x^{0}$| and implication |$x\rightarrow y$| as the set of all maximal elements |$z$| satisfying |$x\wedge z=0$| and as the set of all maximal elements |$z$| satisfying |$x\wedge z\leq y$|⁠, respectively. Such a negation and implication is ‘unsharp’ since it assigns to one entry |$x$| or to two entries |$x$| and |$y$| belonging to the semilattice, respectively, a subset instead of an element of the semilattice. Surprisingly, this kind of negation and implication still shares a number of properties of these connectives in intuitionistic logic, in particular the derivation rule Modus Ponens. Moreover, unsharp negation and unsharp implication can be characterized by means of five, respectively seven simple axioms. We present several examples. The concepts of a deductive system and of a filter are introduced as well as the congruence determined by such a filter. We finally describe certain relationships between these concepts. (shrink)

This article presents and compares various algebraic structures that arise in axiomatic unsharp quantum physics. We begin by stating some basic principles that such an algebraic structure should encompass. Following G. Mackey and G. Ludwig, we first consider a minimal state-effect-probability (minimal SEFP) structure. In order to include partial operations of sum and difference, an additional axiom is postulated and a SEFP structure is obtained. It is then shown that a SEFP structure is equivalent to an effect (...) algebra with an order determining set of states. We also consider σ-SEFP structures and show that these structures distinguish Hilbert space from incomplete inner product spaces. Various types of sharpness are discussed and under what conditions a Brouwer complementation can be defined to obtain a BZ-poset is investigated. In this case it is shown that every effect has a best lower and upper sharp approximation and that the set of all Brouwer sharp effects form an orthoalgebra. (shrink)

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is (...) ${\rm{\Sigma }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel. (shrink)

This paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

This paper is an abstract of the report which was presented on the Polish-Soviet meeting on logic . It is shown that one can consider a lineary-ordered Heyting’s and Brouwer’s algebras as truth-values for Lukasiewicz’s infinite-valued logic’s Lω.

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)

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)

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)

Neutrosophic theory and its applications have been expanding in all directions at an astonishing rate especially after of the introduction the journal entitled “Neutrosophic Sets and Systems”. New theories, techniques, algorithms have been rapidly developed. One of the most striking trends in the neutrosophic theory is the hybridization of neutrosophic set with other potential sets such as rough set, bipolar set, soft set, hesitant fuzzy set, etc. The different hybrid structures such as rough neutrosophic set, single valued neutrosophic rough (...) set, bipolar neutrosophic set, single valued neutrosophic hesitant fuzzy set, etc. are proposed in the literature in a short period of time. Neutrosophic set has been an important tool in the application of various areas such as data mining, decision making, e-learning, engineering, medicine, social science, and some more. (shrink)

In this book authors for the first time introduce the notion of super interval matrices using special intervals. The advantage of using super interval matrices is that one can build only one vector space using m × n interval matrices, but in case of super interval matrices we can have several such spaces depending on the partition on the interval matrix.

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)

In this paper we present the concept of neutrosophic quadruple algebraic structures. Specially, we study neutrosophic quadruple rings and we present their elementary properties.

In this paper, we recall and study the new type of algebraic structures called Symbolic Plithogenic Algebraic Structures. Their operations are given under the Absorbance Law and the Prevalence Order.

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)

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)

In this paper, constructions of free ordered algebras on one generator are given that correspond to some one-variable fragments of affine propositional classical logic and their extensions with n-contraction (n ≥ 2). Moreover, embeddings of the already known infinite free structures into the algebras introduced below are furnished with; thus, solving along the respective cardinality problems.

In this paper, constructions of free ordered algebras on one generator are given that correspond to some one-variable fragments of affine propositional classical logic and their extensions with n-contraction. Moreover, embeddings of the already known infinite free structures into the algebras introduced below are furnished with; thus, solving along the respective cardinality problems.

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)

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.

Substructural logics are obtained from the sequent calculi for classical or intuitionistic logic by suitably restricting or deleting some or all of the structural rules (Restall, 2000; Ono, 1998). Recently, this field of research has come to encompass a number of logics - e.g. many fuzzy or paraconsistent logics - which had been originally introduced out of different, possibly semantical, motivations. A finer proof-theoretical analysis of such logics, in fact, revealed that it was possible to subsume them under the previous (...) definition (see e.g. Aguzzoli and Ciabattoni, 2000).Although proof systems for substructural logics are currently being investigated with remarkable success, their algebraic models do not seem equally satisfactory. In fact:(i) such structures are often very weak, i.e. they do not possess many interesting algebraic properties;(ii) as a consequence, their theories of ideals, congruences, and representation are as a rule scarcely developed, or even lacking.In this paper, we address these difficulties. (shrink)

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.

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 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)

This paper is devoted to Plithogeny, Plithogenic Set, and its extensions. These concepts are branches of uncertainty and indeterminacy instruments of practical and theoretical interest. Starting with some examples, we proceed towards general structures. Then we present definitions and applications of the principal concepts derived from plithogeny, and relate them to complex problems.

We define an easily verifiable notion of an atomic formula having uniformly bounded arrays in a structure M. We prove that if T is a complete L-theory, then T is mutually algebraic if and only if there is some model M of T for which every atomic formula has uniformly bounded arrays. Moreover, an incomplete theory T is mutually algebraic if and only if every atomic formula has uniformly bounded arrays in every model M of T.

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)

In this paper we present the development from paradoxism to neutrosophy, which gave birth to neutrosophic set and logic and especially to NeutroAlgebraic Structures (or NeutroAlgebras) and AntiAlgebraic Structures (or AntiAlgebras) that are generalizations and alternatives of the classical algebraic structures.

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)

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)

We characterize when the elementary diagram of a mutually algebraic structure has a model complete theory, and give an explicit description of a set of existential formulas to which every formula is equivalent. This characterization yields a new, more constructive proof that the elementary diagram of any model of a strongly minimal, trivial theory is model complete.