Results 1 to 10 of about 396 (66)
Automated Synthesis of Tableau Calculi [PDF]
Logical Methods in Computer Science, 2011 This paper presents a method for synthesising sound and complete tableau calculi. Given a specification of the formal semantics of a logic, the method generates a set of tableau inference rules that can then be used to reason within the logic. The method
Renate A. Schmidt, Dmitry Tishkovsky
doaj +1 more source
Algebraic Elimination of epsilon-transitions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We present here algebraic formulas associating a k-automaton to a k-epsilon-automaton. The existence depends on the definition of the star of matrices and of elements in the semiring k.
Gérard Duchamp +2 more
doaj +1 more source
Solving equations over small unary algebras [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We consider the problem of solving a system of polynomial equations over fixed algebra $A$ which we call MPolSat($A$). We restrict ourselves to unary algebras and give a partial characterization of complexity of MPolSat($A$). We isolate a preorder $P(A)$
Przemyslaw Broniek
doaj +1 more source
Undecidable problems concerning densities of languages [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the ...
Jakub Kozik
doaj +1 more source
Classical Combinatory Logic [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 Combinatory logic shows that bound variables can be eliminated without loss of expressiveness. It has applications both in the foundations of mathematics and in the implementation of functional programming languages.
Karim Nour
doaj +1 more source
Non-Determinism and Nash Equilibria for Sequential Game over Partial Order [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 In sequential games of traditional game theory, backward induction guarantees existence of Nash equilibrium by yielding a sub-game perfect equilibrium.
Stéphane Le Roux
doaj +1 more source
The call-by-value λµ∧∨-calculus [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 In this paper, we introduce the $λ μ ^{∧∨}$ - call-by-value calculus and we give a proof of the Church-Rosser property of this system. This proof is an adaptation of that of Andou (2003) which uses an extended parallel reduction method and complete ...
Karim Nour, Khelifa Saber
doaj +1 more source
On-line coloring of $I_s$-free graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 An on-line vertex coloring algorithm receives vertices of a graph in some externally determined order. Each new vertex is presented together with a set of the edges connecting it to the previously presented vertices.
Iwona Cieslik, Marcin Kozik, Piotr Micek
doaj +1 more source
On-line Adaptive Chain Covering of Upgrowing Posets [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We analyze on-line chain partitioning problem and its variants as a two-person game. One person (Spoiler) builds an on-line poset presenting one point at time. The other one (Algorithm) assigns new point to a chain.
Bartłomiej Bosek, Piotr Micek
doaj +1 more source
Random Boolean expressions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We examine how we can define several probability distributions on the set of Boolean functions on a fixed number of variables, starting from a representation of Boolean expressions by trees.
Danièle Gardy
doaj +1 more source