Log in

Relevant bibliographies by topics / Algorithmic number theory / Journal articles

Journal articles on the topic 'Algorithmic number theory'

To see the other types of publications on this topic, follow the link: Algorithmic number theory.

Author: Grafiati

Published: 4 June 2021

Last updated: 21 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Algorithmic number theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Schoof, Ren\'e. "Book Review: Algorithmic algebraic number theory." Bulletin of the American Mathematical Society 29, no. 1 (July 1, 1993): 111–14. http://dx.doi.org/10.1090/s0273-0979-1993-00392-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

W., H. C., and Michael Pohst. "Algorithmic Methods in Algebra and Number Theory." Mathematics of Computation 55, no. 192 (October 1990): 876. http://dx.doi.org/10.2307/2008461.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Gilman, Robert. "Algorithmic search in group theory." Journal of Algebra 545 (March 2020): 237–44. http://dx.doi.org/10.1016/j.jalgebra.2019.08.021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Roman’kov, V. A. "Algorithmic theory of solvable groups." Prikladnaya Diskretnaya Matematika, no. 52 (2021): 16–64. http://dx.doi.org/10.17223/20710410/52/2.

Full text

Abstract:

The purpose of this survey is to give some picture of what is known about algorithmic and decision problems in the theory of solvable groups. We will provide a number of references to various results, which are presented without proof. Naturally, the choice of the material reported on reflects the author’s interests and many worthy contributions to the field will unfortunately go without mentioning. In addition to achievements in solving classical algorithmic problems, the survey presents results on other issues. Attention is paid to various aspects of modern theory related to the complexity of algorithms, their practical implementation, random choice, asymptotic properties. Results are given on various issues related to mathematical logic and model theory. In particular, a special section of the survey is devoted to elementary and universal theories of solvable groups. Special attention is paid to algorithmic questions regarding rational subsets of groups. Results on algorithmic problems related to homomorphisms, automorphisms, and endomorphisms of groups are presented in sufficient detail.

APA, Harvard, Vancouver, ISO, and other styles

5

Hofmann, Tommy, and Carlo Sircana. "On the computation of overorders." International Journal of Number Theory 16, no. 04 (December 6, 2019): 857–79. http://dx.doi.org/10.1142/s179304212050044x.

Full text

Abstract:

The computation of a maximal order of an order in a semisimple algebra over a global field is a classical well-studied problem in algorithmic number theory. In this paper, we consider the related problems of computing all minimal overorders as well as all overorders of a given order. We use techniques from algorithmic representation theory and the theory of minimal integral ring extensions to obtain efficient and practical algorithms, whose implementation is publicly available.

APA, Harvard, Vancouver, ISO, and other styles

6

Cremona, J. E. "ALGORITHMIC ALGEBRAIC NUMBER THEORY (Encyclopedia of Mathematics and its Applications)." Bulletin of the London Mathematical Society 23, no. 1 (January 1991): 94–97. http://dx.doi.org/10.1112/blms/23.1.94.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Baumslag, Gilbert, Frank B. Cannonito, Derek J. S. Robinson, and Dan Segal. "The algorithmic theory of polycyclic-by-finite groups." Journal of Algebra 142, no. 1 (September 1991): 118–49. http://dx.doi.org/10.1016/0021-8693(91)90221-s.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ushakov, Alexander. "Algorithmic theory of free solvable groups: Randomized computations." Journal of Algebra 407 (June 2014): 178–200. http://dx.doi.org/10.1016/j.jalgebra.2014.02.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Möhring, Rolf H. "Algorithmic graph theory and perfect graphs." Order 3, no. 2 (June 1986): 207–8. http://dx.doi.org/10.1007/bf00390110.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Balakrishnan, Jennifer S. "Coleman integration for even-degree models of hyperelliptic curves." LMS Journal of Computation and Mathematics 18, no. 1 (2015): 258–65. http://dx.doi.org/10.1112/s1461157015000029.

Full text

Abstract:

The Coleman integral is a $p$-adic line integral that encapsulates various quantities of number theoretic interest. Building on the work of Harrison [J. Symbolic Comput. 47 (2012) no. 1, 89–101], we extend the Coleman integration algorithms in Balakrishnan et al. [Algorithmic number theory, Lecture Notes in Computer Science 6197 (Springer, 2010) 16–31] and Balakrishnan [ANTS-X: Proceedings of the Tenth Algorithmic Number Theory Symposium, Open Book Series 1 (Mathematical Sciences Publishers, 2013) 41–61] to even-degree models of hyperelliptic curves. We illustrate our methods with numerical examples computed in Sage.

APA, Harvard, Vancouver, ISO, and other styles

11

Mérai, László. "Values of rational functions in small subgroups of finite fields and the identity testing problem from powers." International Journal of Number Theory 16, no. 02 (September 18, 2019): 219–31. http://dx.doi.org/10.1142/s1793042120500128.

Full text

Abstract:

Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field [Formula: see text] considered as a linear space over a subfield [Formula: see text]. We apply this to the recently introduced algorithmic problem of identity testing of “hidden” polynomials [Formula: see text] and [Formula: see text] over a high degree extension of a finite field, given oracle access to [Formula: see text] and [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

12

Clote, Peter G., and Jeffry L. Hirst. "Reverse mathematics of some topics from algorithmic graph theory." Fundamenta Mathematicae 157, no. 1 (1998): 1–13. http://dx.doi.org/10.4064/fm-157-1-1-13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Asai, Ryo, and Jay Shah. "Algorithmic canonical stratifications of simplicial complexes." Journal of Pure and Applied Algebra 226, no. 9 (September 2022): 107051. http://dx.doi.org/10.1016/j.jpaa.2022.107051.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Schweighofer, Markus. "An algorithmic approach to Schmüdgen's Positivstellensatz." Journal of Pure and Applied Algebra 166, no. 3 (January 2002): 307–19. http://dx.doi.org/10.1016/s0022-4049(01)00041-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Zhang, Zerui, Yuqun Chen, and Leonid A. Bokut. "Some algorithmic problems for Poisson algebras." Journal of Algebra 525 (May 2019): 562–88. http://dx.doi.org/10.1016/j.jalgebra.2019.02.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Umirbaev, Ualbai. "Algorithmic problems for differential polynomial algebras." Journal of Algebra 455 (June 2016): 77–92. http://dx.doi.org/10.1016/j.jalgebra.2016.02.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Radu, Silviu. "An algorithmic approach to Ramanujan’s congruences." Ramanujan Journal 20, no. 2 (September 29, 2009): 215–51. http://dx.doi.org/10.1007/s11139-009-9174-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Ovsyak, V. K., O. V. Ovsyak, and J. V. Petruszka. "ORDER AND ORDERING IN DISCRETE MATHEMATICS AND INFORMATICS." Ukrainian Journal of Information Technology 3, no. 1 (2021): 37–43. http://dx.doi.org/10.23939/ujit2021.03.037.

Full text

Abstract:

The available means of ordering and sorting in some important sections of discrete mathematics and computer science are studied, namely: in the set theory, classical mathematical logic, proof theory, graph theory, POST method, system of algorithmic algebras, algorithmic languages of object-oriented and assembly programming. The Cartesian product of sets, ordered pairs and ordered n-s, the description by means of set theory of an ordered pair, which are performed by Wiener, Hausdorff and Kuratowski, are presented. The requirements as for the relations that order sets are described. The importance of ordering in classical mathematical logic and proof theory is illustrated by the examples of calculations of the truth values of logical formulas and formal derivation of a formula on the basis of inference rules and substitution rules. Ordering in graph theory is shown by the example of a block diagram of the Euclidean algorithm, designed to find the greatest common divisor of two natural numbers. The ordering and sorting of both the instructions formed by two, three and four ordered fields and the existing ordering of instructions in the program of Post method are described. It is shown that the program is formed by the numbered instructions with unique instruction numbers and the presence of the single instruction with number 1. The means of the system of algorithmic algebras, which are used to perform the ordering and sorting in the algorithm theory, are illustrated. The operations of the system of algorithmic algebras are presented, which include Boolean algebra operations generalized to the three-digit alphabet and operator operations of operator algebra. The properties of the composition operation are described, which is intended to describe the orderings of the operators of the operator algebra in the system of algorithmic algebras. The orderings executed by means of algorithmic programming languages are demonstrated by the hypothetical application of the modern object-oriented programming language C#. The program must contain only one method Main () from which the program execution begins. The ARM microprocessor assembly program must have only one ENTRY directive from which the program execution begins.

APA, Harvard, Vancouver, ISO, and other styles

19

Konieczny, Jakub. "Algorithmic classification of noncorrelated binary pattern sequences." Journal of Number Theory 223 (June 2021): 229–54. http://dx.doi.org/10.1016/j.jnt.2020.10.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Sapir, Mark V. "Algorithmic Problems for Amalgams of Finite Semigroups." Journal of Algebra 229, no. 2 (July 2000): 514–31. http://dx.doi.org/10.1006/jabr.1999.8138.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Sapir, Mark V. "Algorithmic Problems for Amalgams of Finite Semigroups." Journal of Algebra 232, no. 2 (October 2000): 767–85. http://dx.doi.org/10.1006/jabr.2000.8559.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Steinberg, B. "On Algorithmic Problems for Joins of Pseudovarieties." Semigroup Forum 62, no. 1 (January 2001): 1–40. http://dx.doi.org/10.1007/pl00020979.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Abrahão, Felipe S., Klaus Wehmuth, Hector Zenil, and Artur Ziviani. "Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks." Entropy 23, no. 7 (June 29, 2021): 835. http://dx.doi.org/10.3390/e23070835.

Full text

Abstract:

In this article, we investigate limitations of importing methods based on algorithmic information theory from monoplex networks into multidimensional networks (such as multilayer networks) that have a large number of extra dimensions (i.e., aspects). In the worst-case scenario, it has been previously shown that node-aligned multidimensional networks with non-uniform multidimensional spaces can display exponentially larger algorithmic information (or lossless compressibility) distortions with respect to their isomorphic monoplex networks, so that these distortions grow at least linearly with the number of extra dimensions. In the present article, we demonstrate that node-unaligned multidimensional networks, either with uniform or non-uniform multidimensional spaces, can also display exponentially larger algorithmic information distortions with respect to their isomorphic monoplex networks. However, unlike the node-aligned non-uniform case studied in previous work, these distortions in the node-unaligned case grow at least exponentially with the number of extra dimensions. On the other hand, for node-aligned multidimensional networks with uniform multidimensional spaces, we demonstrate that any distortion can only grow up to a logarithmic order of the number of extra dimensions. Thus, these results establish that isomorphisms between finite multidimensional networks and finite monoplex networks do not preserve algorithmic information in general and highlight that the algorithmic information of the multidimensional space itself needs to be taken into account in multidimensional network complexity analysis.

APA, Harvard, Vancouver, ISO, and other styles

24

KONSTANTINOU, ELISAVET, and ARISTIDES KONTOGEORGIS. "RAMANUJAN INVARIANTS FOR DISCRIMINANTS CONGRUENT TO 5 (mod 24)." International Journal of Number Theory 08, no. 01 (February 2012): 265–87. http://dx.doi.org/10.1142/s1793042112500157.

Full text

Abstract:

In this paper we compute the minimal polynomials of Ramanujan values [Formula: see text] for discriminants D ≡ 5 ( mod 24). Our method is based on Shimura Reciprocity Law as which was made computationally explicit by Gee and Stevenhagen in [Generating class fields using Shimura reciprocity, in Algorithmic Number Theory, Lecture Notes in Computer Science, Vol. 1423 (Springer, Berlin, 1998), pp. 441–453; MR MR1726092 (2000m:11112)]. However, since these Ramanujan values are not class invariants, we present a modification of the method used in [Generating class fields using Shimura reciprocity, in Algorithmic Number Theory, Lecture Notes in Computer Science, Vol. 1423 (Springer, Berlin, 1998), pp. 441–453; MR MR1726092 (2000m:11112)] which can be applied on modular functions that do not necessarily yield class invariants.

APA, Harvard, Vancouver, ISO, and other styles

25

Geck, Meinolf. "On Jacob's construction of the rational canonical form of a matrix." Electronic Journal of Linear Algebra 36, no. 36 (April 4, 2020): 177–82. http://dx.doi.org/10.13001/ela.2020.5055.

Full text

Abstract:

H.G. Jacob's elegant approach to the rational canonical, or Frobenius normal form of a linear map is presented here in pure matrix language, thereby avoiding the abstract machinery and prerequisites in the original paper. Related algorithmic aspects and an efficient implementation in the computer algebra system GAP are also discussed.

APA, Harvard, Vancouver, ISO, and other styles

26

Green, Edward L., and Øyvind Solberg. "An algorithmic approach to resolutions." Journal of Symbolic Computation 42, no. 11-12 (November 2007): 1012–33. http://dx.doi.org/10.1016/j.jsc.2007.05.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

KALKBRENER, M. "Algorithmic Properties of Polynomial Rings." Journal of Symbolic Computation 26, no. 5 (November 1998): 525–81. http://dx.doi.org/10.1006/jsco.1998.0227.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Cerri, Jean-Paul. "Euclidean minima of totally real number fields: Algorithmic determination." Mathematics of Computation 76, no. 259 (February 27, 2007): 1547–76. http://dx.doi.org/10.1090/s0025-5718-07-01932-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

GAIFULLIN, ALEXANDER A., and VASSILY O. MANTUROV. "ON THE RECOGNITION OF BRAIDS." Journal of Knot Theory and Its Ramifications 11, no. 08 (December 2002): 1193–209. http://dx.doi.org/10.1142/s0218216502002207.

Full text

Abstract:

A simple complete combinatorial invariant for elements of the braid group is found. It admits some generalizations, e.g. a complete invariant of spherical braids and a complete invariant of cylindrical braids. Values of the invariants are well recognizable, i.e., they provide the complete algorithmic classification of elements in the named braid groups.

APA, Harvard, Vancouver, ISO, and other styles

30

Perlwitz, Marcela D. "Dividing Fractions: Reconciling Self-Generated Solutions with Algorithmic Answers." Mathematics Teaching in the Middle School 10, no. 6 (February 2005): 278–83. http://dx.doi.org/10.5951/mtms.10.6.0278.

Full text

Abstract:

In this Article, I Discuss Some Key Episodes that occurred in one of my mathematics classes on basic arithmetic notions. The core concepts of the course included place-value numeration, whole numbers and operations, fractions and operations, and foundations of number theory.

APA, Harvard, Vancouver, ISO, and other styles

31

Kramosil, Ivan. "On Pseudo-Random Sequences over Finite Automata." Fundamenta Informaticae 8, no. 1 (January 1, 1985): 55–62. http://dx.doi.org/10.3233/fi-1985-8104.

Full text

Abstract:

It is a well-known fact that binary sequences (strings) of high algorithmic complexity can be taken as good approximations of statistically independent random sequences with two equiprobable outputs. Here “sequence of high algorithmic complexity” is such one, that the length of the shortest program generating this sequence by a universal Turing machine differs only by an a priori given constant from the length of the generated sequence. The present paper generalizes this result to the case of a finite (not necessarily binary) alphabet. Considering an infinite sequence of finite sequences of high algorithmic complexity over a finite alphabet, the relative frequency of occurences of each letter or finite string of letters is proved to tend to the inverted value of the total number of letters, or strings of letters of the given length, in question. This result may be seen as an analogy to the strong law of large numbers in the case of equiprobable probability distribution.

APA, Harvard, Vancouver, ISO, and other styles

32

Goodwin, Simon. "Algorithmic testing for dense orbits of Borel subgroups." Journal of Pure and Applied Algebra 197, no. 1-3 (May 2005): 171–81. http://dx.doi.org/10.1016/j.jpaa.2004.08.038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

SWENTON, FRANK J. "ALGORITHMIC CONSTRUCTION OF KIRBY DIAGRAMS FOR BRANCHED COVERS." Journal of Knot Theory and Its Ramifications 13, no. 07 (November 2004): 939–45. http://dx.doi.org/10.1142/s0218216504003561.

Full text

Abstract:

We present an algorithm that converts any description of a 3-manifold as a finite-sheeted cover of the 3-sphere, branched over some knot or knotted graph, into a Kirby diagram for that manifold, thus resolving the problem posed in [4].

APA, Harvard, Vancouver, ISO, and other styles

34

Nobile, Augusto. "On the use of naturality in algorithmic resolution." Journal of Algebra 324, no. 8 (October 2010): 1887–902. http://dx.doi.org/10.1016/j.jalgebra.2010.06.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Delgado, Jordi, and Enric Ventura. "Algorithmic problems for free-abelian times free groups." Journal of Algebra 391 (October 2013): 256–83. http://dx.doi.org/10.1016/j.jalgebra.2013.04.033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

BAEZ, JOHN, and MIKE STAY. "Algorithmic thermodynamics." Mathematical Structures in Computer Science 22, no. 5 (September 6, 2012): 771–87. http://dx.doi.org/10.1017/s0960129511000521.

Full text

Abstract:

Algorithmic entropy can be viewed as a special case of the entropy studied in statistical mechanics. This viewpoint allows us to apply many techniques developed for use in thermodynamics to the subject of algorithmic information theory. In particular, suppose we fix a universal prefix-free Turing machine and let X be the set of programs that halt for this machine. Then we can regard X as a set of ‘microstates’, and treat any function on X as an ‘observable’. For any collection of observables, we can study the Gibbs ensemble that maximises entropy subject to constraints on the expected values of these observables. We illustrate this by taking the log runtime, length and output of a program as observables analogous to the energy E, volume V and number of molecules N in a container of gas. The conjugate variables of these observables allow us to define quantities we call the ‘algorithmic temperature’ T, ‘algorithmic pressure’ P and ‘algorithmic potential’ μ, since they are analogous to the temperature, pressure and chemical potential. We derive an analogue of the fundamental thermodynamic relation dE = TdS − PdV + μdN, and use it to study thermodynamic cycles analogous to those for heat engines. We also investigate the values of T, P and μ for which the partition function converges. At some points on the boundary of this domain of convergence, the partition function becomes uncomputable – indeed, at these points the partition function itself has non-trivial algorithmic entropy.

APA, Harvard, Vancouver, ISO, and other styles

37

Povhan, Igor. "Method of algorithmic classification trees based on constraints." Bulletin of the National Technical University "KhPI" A series of "Information and Modeling", no. 1 (5) (October 25, 2021): 17–38. http://dx.doi.org/10.20998/2411-0558.2021.01.02.

Full text

Abstract:

The general problem of constructing algorithmic recognition (classification) trees based on a limited method in the theory of artificial intelligence is considered. The object of this research is the concept of an algorithmic classification tree based on a bounded method. The subject of the research is actual methods, algorithms and schemes (limited method) for constructing algorithmic classification trees. A limited method for constructing algorithmic classification trees is proposed, which for a given initial training sample of any size builds a tree structure (algorithm tree model), which consists of a set of autonomous classification algorithms and recognition evaluated at each stage of constructing algorithm trees based on this initial sample. That is, a limited method for constructing an algorithmic classification tree is proposed, the main idea of which is a step-by-step approximation of the initial sample of an arbitrary volume and structure by a set of independent classification and recognition algorithms. This method, when forming the current vertex of the algorithmic tree, ensures that the most efficient (high-quality) autonomous classification algorithms are selected from the initial set and only those paths in the tree structure where the greatest number of classification errors occur are completed. The limited method of constructing an algorithmic classification tree makes it possible to build different types of tree-like recognition models with predefined accuracy for a wide class of problems in the theory of artificial intelligence. The limited method of the algorithmic classification tree developed and presented in this paper received a software implementation and was investigated and compared with the methods of logical classification trees, methods of the algorithmic classification tree (first and second types) when solving the problem of recognizing real geological data. Figs.: 2. Tabl.: 1. Refs.: 34 titles.

APA, Harvard, Vancouver, ISO, and other styles

38

MORA, CATERINA E., and HANS J. BRIEGEL. "ALGORITHMIC COMPLEXITY OF QUANTUM STATES." International Journal of Quantum Information 04, no. 04 (August 2006): 715–37. http://dx.doi.org/10.1142/s0219749906002043.

Full text

Abstract:

We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.

APA, Harvard, Vancouver, ISO, and other styles

39

Wang, Chao, Shuang Wang, Wei Chen, Zhen-Qiang Yin, and Zheng-Fu Han. "Analysis of entropy extraction efficiencies in random number generation systems." International Journal of Quantum Information 14, no. 01 (February 2016): 1630001. http://dx.doi.org/10.1142/s0219749916300011.

Full text

Abstract:

Random numbers (RNs) have applications in many areas: lottery games, gambling, computer simulation, and, most importantly, cryptography [N. Gisin et al., Rev. Mod. Phys. 74 (2002) 145]. In cryptography theory, the theoretical security of the system calls for high quality RNs. Therefore, developing methods for producing unpredictable RNs with adequate speed is an attractive topic. Early on, despite the lack of theoretical support, pseudo RNs generated by algorithmic methods performed well and satisfied reasonable statistical requirements. However, as implemented, those pseudorandom sequences were completely determined by mathematical formulas and initial seeds, which cannot introduce extra entropy or information. In these cases, “random” bits are generated that are not at all random. Physical random number generators (RNGs), which, in contrast to algorithmic methods, are based on unpredictable physical random phenomena, have attracted considerable research interest. However, the way that we extract random bits from those physical entropy sources has a large influence on the efficiency and performance of the system. In this manuscript, we will review and discuss several randomness extraction schemes that are based on radiation or photon arrival times. We analyze the robustness, post-processing requirements and, in particular, the extraction efficiency of those methods to aid in the construction of efficient, compact and robust physical RNG systems.

APA, Harvard, Vancouver, ISO, and other styles

40

Bolotin, Arkady. "Examples of Non-Constructive Proofs in Quantum Theory." Applied Physics Research 8, no. 1 (November 30, 2015): 1. http://dx.doi.org/10.5539/apr.v8n1p1.

Full text

Abstract:

<p class="1Body">Unlike mathematics, in which the notion of truth might be abstract, in physics, the emphasis must be placed on algorithmic procedures for obtaining numerical results subject to the experimental verifiability. For, a physical science is exactly that: algorithmic procedures (built on a certain mathematical formalism) for obtaining verifiable conclusions from a set of basic hypotheses. By admitting non-constructivist statements, a physical theory loses its concrete applicability and thus verifiability of its predictions. Accordingly, the requirement of constructivism must be indispensable to any physical theory. Nevertheless, in at least some physical theories, and especially in quantum mechanics, one can find examples of non-constructive statements. The present paper demonstrates a couple of such examples dealing with macroscopic quantum states (i.e., with the applicability of the standard quantum formalism to macroscopic systems). As it is shown, in these examples the proofs of the existence of macroscopic quantum states are based on logical principles allowing one to decide the truth of predicates over an infinite number of things.</p>

APA, Harvard, Vancouver, ISO, and other styles

41

Pasztor, Ana. "Non-standard algorithmic and dynamic logic." Journal of Symbolic Computation 2, no. 1 (March 1986): 59–81. http://dx.doi.org/10.1016/s0747-7171(86)80013-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

CALVEZ, MATTHIEU, and BERT WIEST. "FAST ALGORITHMIC NIELSEN–THURSTON CLASSIFICATION OF FOUR-STRAND BRAIDS." Journal of Knot Theory and Its Ramifications 21, no. 05 (April 2012): 1250043. http://dx.doi.org/10.1142/s0218216511009959.

Full text

Abstract:

We give an algorithm which decides the Nielsen–Thurston type of a given four-strand braid. The complexity of our algorithm is quadratic with respect to word length. The proof of its validity is based on a result which states that for a reducible 4-braid which is as short as possible within its conjugacy class (short in the sense of Garside), reducing curves surrounding three punctures must be round or almost round. As an application, we give a polynomial time solution to the conjugacy problem for non-pseudo-Anosov four-strand braids.

APA, Harvard, Vancouver, ISO, and other styles

43

KUČERA, ANTONÍN, ANDRÉ NIES, and CHRISTOPHER P. PORTER. "DEMUTH’S PATH TO RANDOMNESS." Bulletin of Symbolic Logic 21, no. 3 (September 2015): 270–305. http://dx.doi.org/10.1017/bsl.2015.24.

Full text

Abstract:

AbstractOsvald Demuth (1936–1988) studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on (i) Demuth’s work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, (ii) Demuth’s independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and (iii) the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth’s work.

APA, Harvard, Vancouver, ISO, and other styles

44

DIEKERT, VOLKER, and ALEXEI MYASNIKOV. "GROUP EXTENSIONS OVER INFINITE WORDS." International Journal of Foundations of Computer Science 23, no. 05 (August 2012): 1001–19. http://dx.doi.org/10.1142/s0129054112400424.

Full text

Abstract:

Non-Archimedean words have been introduced as a new type of infinite words which can be investigated through classical methods in combinatorics on words due to a length function. The length function, however, takes values in the additive group of polynomials ℤ[t] (and not, as traditionally, in ℕ), which yields various new properties. Non-Archimedean words allow to solve a number of interesting algorithmic problems in geometric and algorithmic group theory. There is also a connection to logic and the first-order theory in free groups (Tarski Problems). In the present paper we provide a general method to use infinite words over a discretely ordered abelian group as a tool to investigate certain group extensions for an arbitrary group G. The central object is a group E (A, G) which is defined in terms of a non-terminating, but confluent rewriting system. The groupG as well as some natural HNN-extensions of G embed into E (A, G) (and still "behave like" G), which makes it interesting to study its algorithmic properties. In order to show that every group G embeds into E (A, G) we combine methods from combinatorics on words, string rewriting and group theory.

APA, Harvard, Vancouver, ISO, and other styles

45

Branco, M. B., I. Ojeda, and J. C. Rosales. "Almost symmetric numerical semigroups with given Frobenius number and type." Journal of Algebra and Its Applications 18, no. 11 (August 19, 2019): 1950217. http://dx.doi.org/10.1142/s0219498819502177.

Full text

Abstract:

We give two algorithmic procedures to compute the whole set of almost symmetric numerical semigroups with fixed Frobenius number and type, and the whole set of almost symmetric numerical semigroups with fixed Frobenius number. Our algorithms allow to compute the whole set of almost symmetric numerical semigroups with fixed Frobenius number with similar or even higher efficiency that the known ones. They have been implemented in the GAP [The GAP Group, GAP — Groups, Algorithms and Programming, Version 4.8.6; 2016, https://www.gap-system.org ] package NumericalSgps [M. Delgado and P. A. García-Sánchez and J. Morais, “numericalsgps”: A GAP package on numerical semigroups, https://github.com/gap-packages/numericalsgps ].

APA, Harvard, Vancouver, ISO, and other styles

46

Stepaniuk, Jarosław. "Applications of Finite Models Properties in Approximation and Algorithmic Logics." Fundamenta Informaticae 14, no. 1 (January 1, 1991): 91–108. http://dx.doi.org/10.3233/fi-1991-14105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Wheeler, Billy. "Simplicity, Language-Dependency and the Best System Account of Laws." THEORIA. An International Journal for Theory, History and Foundations of Science 31, no. 2 (May 24, 2016): 189. http://dx.doi.org/10.1387/theoria.14558.

Full text

Abstract:

It is often said that the best system account of laws (BSA) needs supplementing with a theory of perfectly natural properties. The ‘strength’ and ‘simplicity’ of a system is language-relative and without a fixed vocabulary it is impossible to compare rival systems. Recently a number of philosophers have attempted to reformulate the BSA in an effort to avoid commitment to natural properties. I assess these proposals and argue that they are problematic as they stand. Nonetheless, I agree with their aim, and show that if simplicity is interpreted as ‘compression’, algorithmic information theory provides a framework for system comparison without the need for natural properties.

APA, Harvard, Vancouver, ISO, and other styles

48

Flores, Ramón, Delaram Kahrobaei, and Thomas Koberda. "Algorithmic problems in right-angled Artin groups: Complexity and applications." Journal of Algebra 519 (February 2019): 111–29. http://dx.doi.org/10.1016/j.jalgebra.2018.10.023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Liu, Ricky Ini. "An algorithmic Littlewood-Richardson rule." Journal of Algebraic Combinatorics 31, no. 2 (January 21, 2010): 253–66. http://dx.doi.org/10.1007/s10801-009-0184-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Razvenskaya, Olga O. "On new algorithmic techniques for the weighted vertex coloring problem." Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva 22, no. 4 (December 31, 2020): 442–48. http://dx.doi.org/10.15507/2079-6900.22.202004.442-448.

Full text

Abstract:

The classical NP-hard weighted vertex coloring problem consists in minimizing the number of colors in colorings of vertices of a given graph so that, for each vertex, the number of its colors equals a given weight of the vertex and adjacent vertices receive distinct colors. The weighted chromatic number is the smallest number of colors in these colorings. There are several polynomial-time algorithmic techniques for designing efficient algorithms for the weighted vertex coloring problem. For example, standard techniques of this kind are the modular graph decomposition and the graph decomposition by separating cliques. This article proposes new polynomial-time methods for graph reduction in the form of removing redundant vertices and recomputing weights of the remaining vertices so that the weighted chromatic number changes in a controlled manner. We also present a method of reducing the weighted vertex coloring problem to its unweighted version and its application. This paper contributes to the algorithmic graph theory.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!