Representation of a non zero integer as a signed product of primes is unique similarly to its representations in various types of positional notations [4], [3]. The study focuses on counting the prime factors of integers in the form of sums or differences of two equal powers (thus being represented by 1 and a series of zeroes in respective digital bases). Although the introduced theorems are not particularly important, they provide a couple of shortcuts useful for integer factorization, which could serve in further development of Mizar projects [2]. This could be regarded as one of the important benefits of proof formalization [9].
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We present an operational semantics for time-aware business processes, that is, processes modeling the execution of business activities, whose durations are subject to linear constraints over the integers. We assume that some of the durations are controllable, that is, they can be determined by the organization that executes the process, while others are uncontrollable, that is, they are determined by the external world. Then, we consider controllability properties, which guarantee the completion of the execution of the process, satisfying the given duration constraints, independently of the values of the uncontrollable durations. Controllability properties are encoded by quantified reachability formulas, where the reachability predicate is recursively defined by means of constrained Horn clauses (CHCs). These clauses are automatically derived from the operational semantics of the process. Finally, we present two algorithms for solving the so called weak and strong controllability problems. Our algorithms reduce these problems to the verification of a set of quantified integer constraints, which are simpler than the original quantified reachability formulas, and can effectively be handled by state-of-the-art CHC solvers.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We briefly survey some results and open problems on word equations, especially on those equations where the right-hand side is a power of a variable. We discuss a method that was recently used to prove one of the results, and we prove improved versions of some lemmas that are related to the method and can be used as tools when studying word equations. We use the method and the tools to give new, simple proofs for several old results.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
There are well known problems which are not decidable: halting problem, provability in PA, being a first order tautology, and others. Since all these problem deal with notions like computability and provability, they are beyond the scope of “usual” mathematics - mathematical analysis, for instance. Here, we will show a bunch of examples of simple undecidable statements of such mathematics.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor – a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giantstep method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We consider the model checking problem for Gap-order Constraint Systems (GCS) w.r.t. the branching-time temporal logic CTL, and in particular its fragments EG and EF. GCS are nondeterministic infinitely branching processes described by evolutions of integer-valued variables, subject to Presburger constraints of the form x−y ≥ k, where x and y are variables or constants and k ∈ N is a non-negative constant. We show that EG model checking is undecidable for GCS, while EF is decidable. In particular, this implies the decidability of strong and weak bisimulation equivalence between GCS and finite-state systems.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let En = {xi = 1; xi + xj = xk; xi · xj = xk : i; j; k ∈ {1,...,n}}. We conjecture that if a system S ⊆ En has only finitely many solutions in integers x1,...,xn, then each such solution (x1,...,xn) satisfies |x1|,...,|xn| ≤ 22n−1. Assuming the conjecture, we prove: (1) there is an algorithm which to each Diophantine equation assigns an integer which is greater than the heights of integer (non-negative integer, rational) solutions, if these solutions form a finite set, (2) if a set M Í \mathbbN is recursively enumerable but not recursive, then a finite-fold Diophantine representation of M does not exist.
The stability of fractional standard and positive continuous-time linear systems with state matrices in integer and rational powers is addressed. It is shown that the fractional systems are asymptotically stable if and only if the eigenvalues of the state matrices satisfy some conditions imposed on the phases of the eigenvalues. The fractional standard systems are unstable if the state matrices have at least one positive eigenvalue.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.