Complexity of counting first-order logic for the subword order
From MaRDI portal
Publication:5089232
DOI10.4230/LIPICS.MFCS.2020.61MaRDI QIDQ5089232FDOQ5089232
Authors: Dietrich Kuske, Christian Schwarz 
Publication date: 18 July 2022
Recommendations
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
- Decidability in the logic of subsequences and supersequences
- Definability in the Subword Order
- Title not available (Why is that?)
- Piecewise testable languages and nondeterministic automata
- On Boolean combinations forming piecewise testable languages
- Title not available (Why is that?)
- Languages ordered by the subword order
- Defining recursive predicates in graph orders
- The subtrace order and counting first-order logic
Cited In (7)
- The height of piecewise-testable languages with applications in logical complexity
- Complexity Results for First-Order Two-Variable Logic with Counting
- Existential Definability over the Subword Ordering
- First-order separation over countable ordinals
- The subtrace order and counting first-order logic
- 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)
