Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn parametrical expressibility in the free void-generated diagonalizable algebra
355
0
0.0
(
0
)
Added by
Andrei Rusu
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Andrei Rusu
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 in 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 nonisomorphic 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 satisfy 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 quantify 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
