Descriptive complexity and weighted Turing machines

DOI10.1016/J.IC.2026.105446MaRDI QIDQ7262280zbMATH OpenFDO

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

Publication date 11 June 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105446

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
• A very hard log-space counting class
• 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: a new perspective
• Descriptive complexity of \(\#\)P functions
• 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 1324669 (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?)
• Logical characterizations of weighted complexity classes
• On the computing power of fuzzy Turing machines
• On the definition of a family of automata
• 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 logics meet computational complexity
• Weighted automata and weighted logics

This page was built for publication: Descriptive complexity and weighted Turing machines

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