Rice and Rice‐Shapiro Theorems for transfinite correction grammars

Hay and, then, Johnson extended the classic Rice and Rice‐Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work (with some motivations presented) to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, $\mathcal {O}$. Other cases are done for all transfinite notations in a very natural, proper subsystem $\mathcal {O}_{\mathrm{Cantor}}$ of $\mathcal {O}$, where $\mathcal {O}_{\mathrm{Cantor}}$ has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in $(\mathcal {O} -\mathcal {O}_{\mathrm{Cantor}})$.     

Uncomputability and undecidability in economic theory

Economic theory, game theory and mathematical statistics have all increasingly become algorithmic sciences. Computable Economics, Algorithmic Game Theory[Noam Nisan, Tim Roiughgarden, Éva Tardos, Vijay V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, Cambridge, 2007] and Algorithmic Statistics[Péter Gács, John T. Tromp, Paul M.B. Vitányi, Algorithmic statistics, IEEE Transactions on Information Theory 47 (6) (2001) 2443-2463] are frontier research subjects. All of them, each in its own way, are underpinned by (classical) recursion theory - and its applied branches, say computational complexity theory or algorithmic information theory - and, occasionally, proof theory. These research paradigms have posed new mathematical and metamathematical questions and, inadvertently, undermined the traditional mathematical foundations of economic theory. A concise, but partial, pathway into these new frontiers is the subject matter of this paper. Interpreting the core of mathematical economic theory to be defined by General Equilibrium Theory and Game Theory, a general - but concise - analysis of the computable and decidable content of the implications of these two areas are discussed. Issues at the frontiers of macroeconomics, now dominated by Recursive Macroeconomic Theory (The qualification ‘recursive’ here has nothing to do with ‘recursion theory’. Instead, this is a reference to the mathematical formalizations of the rational economic agent’s intertemporal optimization problems, in terms of Markov Decision Processes, (Kalman) Filtering and Dynamic Programming, where a kind of ‘recursion’ is invoked in the solution methods. The metaphor of the rational economic agent as a ‘signal processor’ underpins the recursive macroeconomic paradigm.), are also tackled, albeit ultra briefly. The point of view adopted is that of classical recursion theory and varieties of constructive mathematics.     

Decidability of the representation extension property for finite semigroups

We prove that the decision problem of whether or not a finite semigroup has the representation extension property is decidable.     

Decidability of finite quasivarieties generated by certain transformation semigroups

No Abstract. Received January 2, 2000; accepted in final form August 28, 2000.     

Decidability of the Admissibility Problem for Inference Rules in Some <Emphasis Type="Italic">S</Emphasis>5<Subscript>t</Subscript>-Logics

We examine some many-modal logics extending S5_t, t ∈ N, for decidability w.r.t. admissibility of inference rules, and for the logics in question, we prove an algorithmic criterion determining whether the inference rules in them are admissible.__________Translated from Algebra i Logika, Vol. 44, No. 4, pp. 438–458, July–August, 2005.     

Squares of regular languages

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context‐free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Structure theorem for tournaments omitting N5

A finite tournament T is tight if the class of finite tournaments omitting T is well‐quasi‐ordered. We show here that a certain tournament N₅ on five vertices is tight. This is one of the main steps in an exact classification of the tight tournaments, as explained in [10]; the third and final step is carried out in [11]. The proof involves an encoding of the indecomposable tournaments omitting N₅ by a finite alphabet, followed by an application of Kruskal's Tree Theorem. This problem arises in model theory and in computational complexity in a more general form, which remains open: the problem is to give an effective criterion for a finite set {T₁,…,T_k} of finite tournaments to be tight in the sense that the class of all finite tournaments omitting each of T₁,…,T_k is well‐quasi‐ordered. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 165–192, 2003     

AN ELEMENTARY SYSTEM AS AND ITS SEMI-COMPLETENESS AND DECIDABILITY

The author establishes an elementary system AS which contains functions +, ? and a constant 0 and then proves the semi-completeness and the decidability of AS, using the theory of systems of inequalities.     

A Characterization of Finitely Decidable Congruence Modular Varieties

For every finitely generated, congruence modular variety of finite type we find a finite family of finite rings such that the variety is finitely decidable if and only if is congruence permutable and residually small, all solvable congruences in finite algebras from are Abelian, each congruence above the centralizer of the monolith of a subdirectly irreducible algebra from is comparable with all congruences of , each homomorphic image of a subdirectly irreducible algebra with a non-Abelian monolith has a non-Abelian monolith, and, for each ring from , the variety of -modules is finitely decidable.

     

Removing dead transitions in timed-arc Petri nets

Timed-arc Petri nets (TAPNs) are a timed extension of Petri nets where tokens are assigned an age indicating the time elapsed from its creation, and PT-arcs (place to transition arcs) are labelled with time intervals that are used to restrict the age of the tokens that can be used to fire the adjacent transition. This is a rather pathological model, as reachability is undecidable, whereas some other known properties of Petri nets, like boundedness, coverability and even termination, are decidable. This article focuses on the problem of detecting dead transitions, i.e. transitions that can be removed from the model since they can never become enabled. We prove that this problem is decidable for TAPNs with natural times, and we present an algorithm that can be used to find dead transitions in the particular case of 1-safe TAPNs.