Alternating complexity of counting first-order logic for the subword order

DOI10.1007/s00236-022-00424-2OpenAlexW4283525820MaRDI QIDQ2687036

Dietrich Kuske, Christian Schwarz

Publication date: 1 March 2023

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-022-00424-2

Mathematics Subject Classification ID

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

Cites Work

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

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