Logical characterizations of weighted complexity classes

DOI10.4230/LIPICS.MFCS.2024.14MaRDI QIDQ7241012zbMATH OpenFDO

Authors Guillermo Badia, Manfred Droste, Carles Noguera, Erik Paul

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2024.14

zbMATH Keywords

descriptive complexitysemiringsweighted logicsweighted Turing machines

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
• A logical characterization of the counting hierarchy
• A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties
• Capturing complexity classes by fragments of second-order logic
• Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines
• Closure properties and witness reduction
• Computer Science Logic
• Descriptive complexity for counting complexity classes
• Descriptive complexity of \(\#\)P functions
• Descriptive complexity of \#P functions: a new perspective
• Digital image compression
• Elements of automata theory. Translated from the French by Reuben Thomas
• Elements of finite model theory.
• Finite model theory and its applications.
• Fixed-point extensions of first-order logic
• Gap-definable counting classes
• Handbook of weighted automata
• scientific article; zbMATH DE number 4180775 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• On the computing power of fuzzy Turing machines
• On the definition of a family of automata
• On the power of parity polynomial time
• Polynomial Space Counting Problems
• Provenance analysis for logic and games
• Qualitative relativizations of complexity classes
• Relational queries computable in polynomial time
• Semiring reasoning frameworks in AI and their computational complexity
• Space-efficient informational redundancy
• The Complexity of Enumeration and Reliability Problems
• The complexity of optimization problems
• The complexity of tensor calculus
• The equivalence problem for deterministic pushdown automata is decidable
• The equivalence problem of multitape finite automata
• Weighted automata and weighted logics

Cited in

(1)

• Descriptive complexity and weighted Turing machines

This page was built for publication: Logical characterizations of weighted complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241012)