Search results for "TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS"

Nonlocal Quantum XOR Games for Large Number of Players

2010

Nonlocal games are used to display differences between classical and quantum world In this paper, we study nonlocal games with a large number of players We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player, a subclass of nonlocal games We illustrate those methods on the example of the N-player game (due to Ardehali [Ard92]) that provides the maximum quantum-over-classical advantage.

Equivalence closure in the two-variable guarded fragment

2015

We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.

Transformations that preserve learnability

1996

We consider transformations (performed by general recursive operators) mapping recursive functions into recursive functions. These transformations can be considered as mapping sets of recursive functions into sets of recursive functions. A transformation is said to be preserving the identification type I, if the transformation always maps I-identifiable sets into I-identifiable sets.

2018

This study investigated participants’ conceptions of the ideal mentor and mentee in the Finnish model of peer-group mentoring (PGM). Existing mentoring research emphasises dyadic practices, yet the...

Minimal forbidden words and symbolic dynamics

1996

We introduce a new complexity measure of a factorial formal language L: the growth rate of the set of minimal forbidden words. We prove some combinatorial properties of minimal forbidden words. As main result we prove that the growth rate of the set of minimal forbidden words for L is a topological invariant of the dynamical system defined by L.

Collection Principles in Dependent Type Theory

2002

We introduce logic-enriched intuitionistic type theories, that extend intuitionistic dependent type theories with primitive judgements to express logic. By adding type theoretic rules that correspond to the collection axiom schemes of the constructive set theory CZF we obtain a generalisation of the type theoretic interpretation of CZF. Suitable logic-enriched type theories allow also the study of reinterpretations of logic. We end the paper with an application to the double-negation interpretation.

Counting in the Two Variable Guarded Logic with Transitivity

2005

We show that the extension of the two-variable guarded fragment with transitive guards (GF+TG) by functionality statements is undecidable. This gives immediately undecidability of the extension of GF+TG by counting quantifiers. The result is optimal, since both the three-variable fragment of the guarded fragment with counting quantifiers and the two-variable guarded fragment with transitivity are undecidable. We also show that the extension of GF+TG with functionality, where functional predicate letters appear in guards only, is decidable and of the same complexity as GF+TG. This fragment captures many expressive modal and description logics.

Inductive types in homotopy type theory

2012

Homotopy type theory is an interpretation of Martin-L\"of's constructive type theory into abstract homotopy theory. There results a link between constructive mathematics and algebraic topology, providing topological semantics for intensional systems of type theory as well as a computational approach to algebraic topology via type theory-based proof assistants such as Coq. The present work investigates inductive types in this setting. Modified rules for inductive types, including types of well-founded trees, or W-types, are presented, and the basic homotopical semantics of such types are determined. Proofs of all results have been formally verified by the Coq proof assistant, and the proof s…

Rapid construction of algebraic axioms from samples

1991

Abstract An axiom is called reliable if it is confirmed in several places in a given sample of algebra. A very effective algorithm for enumerating such axioms is described.

Efficient Switches with QoS Support for Clusters

2007

Current interconnect standards providing hardware support for quality of service (QoS) consider up to 16 virtual channels (VCs) for this purpose. However, most implementations do not offer so many VCs because they increase the complexity of the switch and the scheduling delays. We have shown that this number of VCs can be significantly reduced, because it is enough to use two VCs for QoS purposes at each switch port. In this paper, we cover the weaknesses of that proposal and, not only we reduce VCs, but we also improve performance due to the flexibility assigning buffer memory.