Fagin's seminal result characterizing NP in terms of existential second-order logic started the fruitful field of descriptive complexity theory. In recent years, there has been much interest in the investigation of quantitative (weighted) models of computations. In this paper, we start the study of descriptive complexity based on weighted Turing machines over arbitrary semirings. We provide machine-independent characterizations (over ordered structures) of the weighted complexity classes NP[S], L[S], FP[S], FPLOG[S], FPSPACE[S], and FPSPACEpoly[S] in terms of definability in suitable weighted logics for an arbitrary semiring S. In particular, we state and prove weighted versions of Fagin's theorem (even for arbitrary structures, not necessarily ordered, provided that the semiring is idempotent and commutative), the Immerman-Vardi's theorem (originally for P) and the Abiteboul-Vianu-Vardi's theorem (originally for PS PACE). We also discuss a recent open problem proposed by Eiter and Kiesel. Recently, the above mentioned weighted complexity classes have been investigated in connection to classical counting complexity classes. Furthermore, several classical counting complexity classes have been characterized in terms of particular weighted logics over the semiring & Nopf; of natural numbers. In this work, we cover several of these classes and obtain new results for others such as NPMV, (R) P, or the collection of real-valued languages realized by nondeterministic polynomial-time real-valued Turing machines. Furthermore, our results apply to classes based on many other important semirings, such as the max-plus and the min-plus semirings over the natural numbers which correspond to the classical classes MaxP[O(log n)] and MinP[O(log n)], respectively.

We show that there is an effectively given zero-sum-free commutative semiring S, contained as the subsemiring of nonnegative elements in an effectively given commutative ordered ring, for which there are no procedures deciding, given a weighted finite automaton over S, whether its support is the language of all words or whether its support is infinite. In particular, by a result of D. Kirsten (2011), since S is zero-sum-free and commutative, the support is recognizable by a classical finite automaton, but such an automaton or even just a pushdown automaton for its support cannot be constructed effectively.

In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of $\omega$-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Sch\"utzenberger 1963). As in the theory of formal grammars, these weighted context-free languages, or $\omega$-algebraic series, can be represented as solutions of mixed $\omega$-algebraic systems of equations and by weighted $\omega$-pushdown automata. In our first main result, we show that (mixed) $\omega$-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple $\omega$-reset pushdown automata recognize all $\omega$-algebraic series. Simple $\omega$-reset automata do not use $\epsilon$-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted context-free languages.

Recently, weighted ω-pushdown automata have been introduced by Droste, Ésik, Kuich. This new type of automaton has access to a stack and models quantitative aspects of infinite words. Here, we consider a simple version of those automata. The simple ω-pushdown automata do not use ε-transitions and have a very restricted stack access. In previous work, we could show this automaton model to be expressively equivalent to context-free ω-languages in the unweighted case. Furthermore, semiring-weighted simple ω-pushdown automata recognize all ω-algebraic series. Here, we consider ω-valuation monoids as weight structures. As a first result, we prove that for this weight structure and for simple ω-pushdown automata, Büchi-acceptance and Muller-acceptance are expressively equivalent. In our second result, we derive a Nivat theorem for these automata stating that the behaviors of weighted ω-pushdown automata are precisely the projections of very simple ω-series restricted to ω-context-free languages. The third result is a weighted logic with the same expressive power as the new automaton model. To prove the equivalence, we use a similar result for weighted nested ω-word automata and apply our present result of expressive equivalence of Muller and Büchi acceptance.

In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of omega-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted languages, or omega-algebraic series, can be represented as solutions of mixed omega-algebraic systems of equations and by weighted omega-pushdown automata. In our first main result, we show that mixed omega-algebraic systems can be transformed into Greibach normal form. Our second main result proves that simple omega-reset pushdown automata recognize all omega-algebraic series that are a solution of an omega-algebraic system in Greibach normal form. Simple reset automata do not use epsilon-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted languages.

By fundamental results of Schützenberger, McNaughton and Papert from the 1970s, the classes of first-order definable and aperiodic languages coincide. Here, we extend this equivalence to a quantitative setting. For this, weighted automata form a general and widely studied model. We define a suitable notion of a weighted first-order logic. Then we show that this weighted first-order logic and aperiodic polynomially ambiguous weighted automata have the same expressive power. Moreover, we obtain such equivalence results for suitable weighted sublogics and finitely ambiguous or unambiguous aperiodic weighted automata. Our results hold for general weight structures, including all semirings, average computations of costs, bounded lattices, and others.

We prove a weighted Feferman-Vaught decomposition theorem for disjoint unions and products of finite structures. The classical Feferman-Vaught Theorem describes how the evaluation of a first order sentence in a generalized product of relational structures can be reduced to the evaluation of sentences in the contributing structures and the index structure. The logic we employ for our weighted extension is based on the weighted MSO logic introduced by Droste and Gastin to obtain a Büchi-type result for weighted automata. We show that for disjoint unions and products of structures, the evaluation of formulas from two respective fragments of the logic can be reduced to the evaluation of formulas in the contributing structures. We also prove that the respective restrictions are necessary. Surprisingly, for the case of disjoint unions, the fragment is the same as the one used in the Büchi-type result of weighted automata. In fact, even the formulas used to show that the respective restrictions are necessary are the same in both cases. However, here proving that they do not allow for a Feferman-Vaught-like decomposition is more complex and employs Ramsey's Theorem. We also show how translation schemes can be applied to go beyond disjoint unions and products.

In the last years renewed investigation of operator precedence languages (OPL) led to discover important properties thereof: OPL are closed with respect to all major operations, are characterized, besides the original grammar family, in terms of an automata family (OPA) and an MSO logic; furthermore they significantly generalize the well-known visibly pushdown languages (VPL). In another area of research, quantitative models of systems are also greatly in demand. In this paper, we lay the foundation to marry these two research fields. We introduce weighted operator precedence automata and show how they are both strict extensions of OPA and weighted visibly pushdown automata. We prove a Nivat-like result which shows that quantitative OPL can be described by unweighted OPA and very particular weighted OPA. In a Büchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL.

We investigate the supports of weighted unranked tree automata. Our main result states that the support of a weighted unranked tree automaton over a zero-sum free, commutative strong bimonoid is recognizable. For this, we use methods of Kirsten (DLT

We present explicit constructions of universal homogeneous objects in categories of domains with stable embedding–projection pairs as arrows. These results make use of a representation of such domains through graph-like structures and apply a generalization of Rado’s result on the existence of the universal homogeneous countable graph. In particular, we build universal homogeneous objects in the categories of coherence spaces and qualitative domains, introduced by Girard (Girard 1987; Girard 1986), and two categories of hypercoherences recently studied by Ehrhard (Ehrhard 1993). Our constructions rely on basic numerical notions. We also show that a suitable random construction of Rado’s graph and its generalizations produces with probability 1 the universal homogeneous structures presented here.

We define the class of divisibility monoids that arise as quotients of the free monoid Σ* modulo certain equations of the form ab = cd. These form a much larger class than free partially commutative monoids, and we show, under certain assumptions, that the recognizable languages in these divisibility monoids coincide with c-rational languages. The proofs rely on Ramsey's theorem, distributive lattice theory and on Hashigushi's rank function generalized to these monoids. We obtain Ochmański's theorem on recognizable languages in free partially commutative monoids as a consequence.

In the theory of denotational semantics of programming languages, several authors have constructed various kinds of universal domains. We present here a categorical generalization of a well-known result in model theory, which we use to characterize large classes of reasonable categories that contain universal homogeneous objects. The existence of such objects is characterized by the condition that the finite objects in the category satisfy the amalgamation property. We derive from this the existence and uniqueness of universal homogeneous domains for several categories of bifinite domains, with embedding-projection-pairs as morphisms. We also obtain universal homogeneous objects for various categories of stable bifinite domains. In contrast, several categories of event domains and concrete domains and the category of all coherent Scott-domains do not contain universal homogeneous objects. Finally, we show that all our constructions can be performed effectively.

In the theory of denotational semantics of programming languages, several authors established the existence of particular kinds of universal domains. Here we consider the categories of all ω-bifinite domain, all ω-bifinite L-domains, all ω-Scott-domains, and all ω-algebraic lattices, respectively, in each case with embedding-projection pairs as morphisms. It has been shown that each of these categories contains a universal homogeneous, or saturated. object. which is unipue up to isomorphism. Here we introduce for each of these four categories l a finite set of axioms Sl, formulated in a first-order language of predicate calculus for posets, and show that an arbitrary domain (D, ≤)ε l is the universal homogeneous object in l if and only if its subset of compact elements satisfies all axioms in Sl.

The authors present a categorical generalization of a well-known result in model theory, the Fraisse-Jonsson theorem, by which they characterize large classes of reasonable categories if they contain universal homogeneous objects. As a first application, they derive from this, for various categories of bifinite domains and with embedding-projection pairs as morphisms, the existence and uniqueness of universal homogeneous objects, and they deduce C.A. Gunter and A. Jung's result (see Logic in Computer Science, Comput. Sci. Press, p.309-19 (1988)) from this. Various categories of stable bifinite domains which apparently have not been considered in the literature before are introduced, and universal homogeneous objects for these categories (with stable embedding-projection pairs) are obtained. For four categories of even domains it is shown that although these categories contain universal objects they do not contain universal homogeneous objects. Finally, it is shown that all the constructions can be performed effectively.>