1.670 hasil
Menampilkan 1–20 · 0,38 detik · RSS
Logical Methods in Computer Science
Scopus
ISSN 1860-5974 · Logical Methods in Computer Science e.V. · 1.670 artikel di indeks
-
Artikel Jurnal
Confluence of conditional rewriting modulo
Sets of equations E play an important computational role in rewriting-based systems R. The equivalence relation =E induced by E introduces a partition of terms into E-equivalence classes on which rewriting computations, denoted ->R/E and called rewriting modulo E, are issued. This paper…
-
Artikel Jurnal
Simply-typed constant-domain modal lambda calculus I: distanced beta reduction and combinatory logic
A system $\boldsymbolλ_θ$ is developed that combines modal logic and simply-typed lambda calculus, and that generalizes the system studied by Montague and Gallin. Whereas Montague and Gallin worked with Church's simple theory of types, the system $\boldsymbolλ_θ$ is developed in the typed base…
-
Artikel Jurnal
The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
We study the question of which visibly pushdown languages (VPLs) are in the complexity class $\mathsf{AC}^0$ and how to effectively decide this question. Our contribution is to introduce a particular subclass of one-turn VPLs, called intermediate VPLs, for which the raised question is entirely…
-
Artikel Jurnal
Policies for Fair Exchanges of Resources
People increasingly use digital platforms to exchange resources in accordance with some policies stating what resources users offer and what they require in return. In this paper, we propose a formal model of these environments, focussing on how users' policies are defined and enforced, so ensuring…
-
Artikel Jurnal
Locality in Residuated-Lattice Structures
Many-valued models generalise the structures from classical model theory by defining truth values for a model with an arbitrary algebra. Just as algebraic varieties provide semantics for many non-classical propositional logics, models defined over algebras in a variety provide the semantics for the…
-
Artikel Jurnal
A Dichotomy Theorem for Ordinal Ranks in MSO
We focus on formulae $\exists X.\, φ(\vec{Y}, X)$ of monadic second-order logic over the full binary tree, such that the witness $X$ is a well-founded set. The ordinal rank $\mathrm{rank}(X) < ω_1$ of such a set $X$ measures its depth and branching structure. We search for the least upper bound for…
-
Artikel Jurnal
Mirroring Call-by-Need, or Values Acting Silly
Call-by-need evaluation for the lambda-calculus can be seen as merging the best of call-by-name and call-by-value, namely the wise erasing behaviour of the former and the wise duplicating behaviour of the latter. To better understand how duplication and erasure can be combined, we design a…
-
Artikel Jurnal
The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic
Modal separability for modal fixpoint formulae is the problem to decide for two given modal fixpoint formulae $φ,φ'$ whether there is a modal formula $ψ$ that separates them, in the sense that $φ\modelsψ$ and $ψ\models\negφ'$. We study modal separability and its special case modal definability over…
-
Artikel Jurnal
JustAct: A Framework for Auditable Multi-Agent Systems Regulated by Inter-Organisational Policies
In open multi-agent agent systems that cross organisational boundaries, agent actions must be regulated by complex policies. Consider medical data processing systems, which must observe generic laws (e.g., EU data protection regulations) and also specific participants' resource conditions (e.g…
-
Artikel Jurnal
Constraint satisfaction problems, compactness and non-measurable sets
A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the existence of homomorphisms from all finite substructures of B to A. We show that if A has width one, then the compactness…
-
Artikel Jurnal
A taxonomy of categories for relations
The study of categories that abstract the structural properties of relations has been extensively developed over the years, resulting in a rich and diverse body of work. This paper strives to provide a modern presentation of these ``categories for relations'', including their enriched version…
-
Artikel Jurnal
A Scalable Game-Theoretic Approach for Selecting Security Controls from Standardized Catalogues
Selecting the combination of security controls that will most effectively protect a system's assets is a difficult task. If the wrong controls are selected, the system may be left vulnerable to cyber-attacks that can impact the confidentiality, integrity, and availability of critical data and…
-
Artikel Jurnal
Dense Integer-Complete Synthesis for Bounded Parametric Timed Automata
Ensuring the correctness of critical real-time systems, involving concurrent behaviours and timing requirements, is crucial. Timed automata extend finite-state automata with clocks, compared in guards and invariants with integer constants. Parametric timed automata (PTAs) extend timed automata with…
-
Artikel Jurnal
A Resolution-Based Interactive Proof System for UNSAT
Modern SAT or QBF solvers are expected to produce correctness certificates. However, certificates have worst-case exponential size (unless NP=coNP), and at recent SAT competitions the largest certificates of unsatisfiability are starting to reach terabyte size. This puts limits to the development…
-
Artikel Jurnal
Univalent Enriched Categories and the Enriched Rezk Completion
Enriched categories are categories whose sets of morphisms are enriched with extra structure. Such categories play a prominent role in the study of higher categories, homotopy theory, and the semantics of programming languages. In this paper, we study univalent enriched categories. We prove that…
-
Artikel Jurnal
First Order Logic on Pathwidth Revisited Again
Courcelle's celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. More…
-
Artikel Jurnal
Prime Factorization in Models of PV$_1$
Assuming that no family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two $n$-bit primes, we show that the bounded arithmetic theory $\text{PV}_1$, even when augmented by the sharply bounded choice scheme $BB(Σ^b_0)$, cannot prove that every number has…
-
Artikel Jurnal
Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same $k$-variable and quantifier-rank-$q$…
-
Artikel Jurnal
Epistemic Skills: Reasoning about Knowledge and Oblivion
This paper presents a class of epistemic logics that captures the dynamics of acquiring knowledge and descending into oblivion, while incorporating concepts of group knowledge. The approach is grounded in a system of weighted models, introducing an ``epistemic skills'' metric to represent the…
-
Artikel Jurnal
The Bright Side of Timed Opacity
Timed automata (TAs) are an extension of finite automata that can measure and react to the passage of time, providing the ability to handle real-time constraints using clocks. In 2009, Franck Cassez showed that the timed opacity problem, where an attacker can observe some actions with their…
Menampilkan maksimal 50 halaman. Persempit pencarian dengan filter untuk hasil yang lebih spesifik.