اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn parametrical expressibility in the free void-generated diagonalizable algebra
359
0
0.0
(
0
)
تأليف
Andrei Rusu
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In the present paper we show that there are infinitely many classes of term functions in the free-void generated diagonalizable algebra, which are precomplete with respect to parametrical expressibility of functions.
قيم البحث
اقرأ أيضاً
In this paper, first-order logic is interpreted in the framework of universal algebra, using the clone theory developed in three previous papers. We first define the free clone T(L, C) of terms of a first order language L over a set C of parameters i
n a standard way. The free right algebra F(L, C) of formulas over T(L, C) is then generated by atomic formulas. Structures for L over C are represented as perfect valuations of F(L, C), and theories of L are represented as filters of F(L). Finally Godels completeness theorem and first incompleteness theorem are stated as expected.
We are interested in solving decision problem $exists? t in mathbb{N}, cos t theta = c$ where $cos theta$ and $c$ are algebraic numbers. We call this the $cos t theta$ problem. This is an exploration of Diophantine equations with analytic functions.
Polynomial, exponential with real base and cosine function are closely related to this decision problem: $ exists ? t in mathbb{N}, u^T M^t v = 0$ where $u, v in mathbb{Q}^n, M in mathbb{Q}^{ntimes n}$. This problem is also known as Skolem problem and is useful in verification of linear systems. Its decidability remains unknown. Single variable Diophantine equations with exponential function with real algebraic base and $cos t theta$ function with $theta$ a rational multiple of $pi$ is decidable. This idea is central in proving the decidability of Skolem problem when the eigenvalues of $M$ are roots of real numbers. The main difficulty with the cases when eigenvalues are not roots of reals is that even for small order cases decidability requires application of trancendental number theory which does not scale for higher order cases. We provide a first attempt to overcome that by providing a $PTIME$ algorithm for $cos t theta$ when $theta$ is not a rational multiple of $pi$. We do so without using techniques from transcendental number theory. par One of the main difficulty in Diophantine equations is being unable to use tools from calculus to solve this equation as the domain of variable is $mathbb{N}$. We also provide an attempt to overcome that by providing reduction of Skolem problem to solving a one variable equation (which involves polynomials, exponentials with real bases and $cos t theta$ function with $t$ ranging over reals and $theta in [0, pi]$) over reals.
We study finitely generated models of countable theories, having at most countably many nonisomorphic finitely generated models. We intro- duce a notion of rank of finitely generated models and we prove, when T has at most countably many nonisomorphi
c finitely generated models, that every finitely generated model has an ordinal rank. This rank is used to give a prop- erty of finitely generated models analogue to the Hopf property of groups and also to give a necessary and sufficient condition for a finitely generated model to be prime of its complete theory. We investigate some properties of limit groups of equationally noetherian groups, in respect to their ranks.
We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G on n vertices admitting a z-topological order- ing, together with such an ordering, one may count the number of subgraphs of G that at the same time sati
sfy a monadic second order formula {phi} and are the union of k directed paths, in time f ({phi}, k, z) * n^O(k*z) . Our result implies the polynomial time solvability of many natural counting problems on digraphs admitting z-topological orderings for constant values of z and k. Concerning the relationship between z-topological orderability and other digraph width measures, we observe that any digraph of directed path-width d has a z- topological ordering for z <= 2d + 1. On the other hand, there are digraphs on n vertices admitting a z-topological order for z = 2, but whose directed path-width is {Theta}(log n). Since graphs of bounded directed path-width can have both arbitrarily large undirected tree-width and arbitrarily large clique width, our result provides for the first time a suitable way of partially trans- posing metatheorems developed in the context of the monadic second order logic of graphs of constant undirected tree-width and constant clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large undirected tree-width and arbitrarily large clique width.
Graded modalities have been proposed in recent work on programming languages as a general framework for refining type systems with intensional properties. In particular, continuous endomaps of the discrete time scale, or time warps, can be used to qu
antify the growth of information in the course of program execution. Time warps form a complete residuated lattice, with the residuals playing an important role in potential programming applications. In this paper, we study the algebraic structure of time warps, and prove that their equational theory is decidable, a necessary condition for their use in real-world compilers. We also describe how our universal-algebraic proof technique lends itself to a constraint-based implementation, establishing a new link between universal algebra and verification technology.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
