The Subtrace Order and Counting First-Order Logic

DOI10.1007/978-3-030-50026-9_21OpenAlexW3036873197MaRDI QIDQ5042249

Dietrich Kuske

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-50026-9_21

zbMATH Keywords

Mazurkiewicz tracescounting logicsubword relation

Mathematics Subject Classification ID

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

Related Items (7)

Absent Subsequences in Words ⋮ Longest Common Subsequence with Gap Constraints ⋮ Alternating complexity of counting first-order logic for the subword order ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Absent subsequences in words ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Definability in the substructure ordering of simple graphs
• Definability in substructure orderings. I: Finite semilattices
• The monadic theory of order
• Languages ordered by the subword order
• Kleene quotient theorems
• Combinatorial problems of commutation and rearrangements
• Theories of orders on the set of words
• Definability in the Subword Order
• Ordering by Divisibility in Abstract Algebras
• Well-structured transition systems everywhere!
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Subtrace Order and Counting First-Order Logic