Languages ordered by the subword order

DOI10.1007/978-3-030-17127-8_20OpenAlexW2910371329MaRDI QIDQ2289086FDOQ2289086

Authors Dietrich Kuske, Georg Zetzsche 

Publication date 28 January 2020

Full work available at URL https://arxiv.org/abs/1901.02194

zbMATH Keywords

decidable theoriesfirst-order logicsubword ordercounting quantifiers

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Complexity of counting first-order logic for the subword order
• Alternating complexity of counting first-order logic for the subword order
• scientific article; zbMATH DE number 7297889
• Theories of orders on the set of words
• The subtrace order and counting first-order logic

Cited In (12)

• Unboundedness problems for machines with reversal-bounded counters
• Longest Common Subsequence with Gap Constraints
• Absent subsequences in words
• Subsequences in bounded ranges: matching and analysis problems
• Existential Definability over the Subword Ordering
• Absent Subsequences in Words
• Complexity of counting first-order logic for the subword order
• The subtrace order and counting first-order logic
• Scattered Factor-Universality of Words
• Combinatorial algorithms for subsequence matching: a survey
• Alternating complexity of counting first-order logic for the subword order
• Preorder-constrained simulations for program refinement with effects

This page was built for publication: Languages ordered by the subword order

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