Complexity of counting first-order logic for the subword order

DOI10.4230/LIPICS.MFCS.2020.61MaRDI QIDQ5089232FDOQ5089232

Authors: Dietrich Kuske, Christian Schwarz 

Publication date: 18 July 2022

Recommendations

• Alternating complexity of counting first-order logic for the subword order
• scientific article; zbMATH DE number 7297889
• The subtrace order and counting first-order logic
• Two-variable first order logic with counting quantifiers: complexity results
• scientific article; zbMATH DE number 7056230

zbMATH Keywords

piecewise testable languagescounting logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Cites Work

• Definability in substructure orderings. I: Finite semilattices
• Definability of Recursive Predicates in the Induced Subgraph Order
• Title not available (Why is that?)
• Title not available (Why is that?)
• Well-structured transition systems everywhere!
• Ordering by Divisibility in Abstract Algebras
• The computational complexity of logical theories
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• Theories of orders on the set of words
• Definability in the \(h\)-quasiorder of labeled forests
• Title not available (Why is that?)
• Definability in the Subword Order
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Boolean combinations forming piecewise testable languages
• Title not available (Why is that?)
• Languages ordered by the subword order
• Title not available (Why is that?)
• The Subtrace Order and Counting First-Order Logic

Cited In (5)

• The Subtrace Order and Counting First-Order Logic
• Complexity Results for First-Order Two-Variable Logic with Counting
• Existential Definability over the Subword Ordering
• Alternating complexity of counting first-order logic for the subword order
• Title not available (Why is that?)

This page was built for publication: Complexity of counting first-order logic for the subword order

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