Results 31 to 40 of about 6,811,260 (293)
On the expressive power of schemes
Information and Computation, 2011 We present a calculus, called the scheme-calculus, that permits to express natural deduction proofs in various theories. Unlike $λ$-calculus, the syntax of this calculus sticks closely to the syntax of proofs, in particular, no names are introduced for the hypotheses.
Dowek, Gilles, Jiang, Ying
openaire +3 more sources
Expressive Power of Linear Algebra Query Languages [PDF]
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2020 Linear algebra algorithms often require some sort of iteration or recursion as is illustrated by standard algorithms for Gaussian elimination, matrix inversion, and transitive closure.
F. Geerts +3 more
semanticscholar +1 more source
Open Linguistics, 2014 This paper considers the questions of translatability and expressive power. It is argued that truthconditional content is always translatable, and does not produce differences in expressive power.
McCready Eric
doaj +1 more source
Musings on Encodings and Expressiveness [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 This paper proposes a definition of what it means for one system description language to encode another one, thereby enabling an ordering of system description languages with respect to expressive power.
Rob van Glabbeek
doaj +1 more source
On Sub-Propositional Fragments of Modal Logic [PDF]
Logical Methods in Computer Science, 2018 In this paper, we consider the well-known modal logics $\mathbf{K}$, $\mathbf{T}$, $\mathbf{K4}$, and $\mathbf{S4}$, and we study some of their sub-propositional fragments, namely the classical Horn fragment, the Krom fragment, the so-called core ...
Davide Bresolin +2 more
doaj +1 more source
THE EXPRESSIVE POWER OF MEMORY LOGICS [PDF]
The Review of Symbolic Logic, 2011 We investigate the expressive power of memory logics. These are modal logics extended with the possibility to store (or remove) the current node of evaluation in (or from) a memory, and to perform membership tests on the current memory. From this perspective, the hybrid logic ℋℒ (↓), for example, can be thought of as a particular case of a memory logic
Areces, Carlos +3 more
openaire +3 more sources
Successor-Invariant First-Order Logic on Classes of Bounded Degree [PDF]
Logical Methods in Computer Science, 2021 We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of an additional successor relation on the structure is allowed, as long as the validity of formulas is independent of the ...
Julien Grange
doaj +1 more source
The Arity Hierarchy in the Polyadic μ-Calculus [PDF]
Electronic Proceedings in Theoretical Computer Science, 2015 The polyadic mu-calculus is a modal fixpoint logic whose formulas define relations of nodes rather than just sets in labelled transition systems. It can express exactly the polynomial-time computable and bisimulation-invariant queries on finite graphs ...
Martin Lange
doaj +1 more source
A note on the expressive power of linear orders [PDF]
Logical Methods in Computer Science, 2011 This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a
Thomas Schwentick, Nicole Schweikardt
doaj +1 more source
On the Expressive Power of 2-Stack Visibly Pushdown Automata [PDF]
Logical Methods in Computer Science, 2008 Visibly pushdown automata are input-driven pushdown automata that recognize some non-regular context-free languages while preserving the nice closure and decidability properties of finite automata. Visibly pushdown automata with multiple stacks have been
Benedikt Bollig
doaj +1 more source