Existential Definability over the Subword Ordering

DOI10.46298/lmcs-19(4:35)2023arXiv2210.15642OpenAlexW4390053600MaRDI QIDQ6178718

Georg Zetzsche, Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Verifying programs with unreliable channels
• Languages ordered by the subword order
• Algorithms for subsequence combinatorics
• On the index of Simon's congruence for piecewise testability
• What makes some language theory problems undecidable
• Searching subsequences
• Unboundedness and downward closures of higher-order pushdown automata
• Computing Downward Closures for Stacked Counter Automata
• Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads
• The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings
• Theories of orders on the set of words
• An Approach to Computing Downward Closures
• Definability in the Subword Order
• The Downward-Closure of Petri Net Languages
• The Complexity of Some Problems on Subsequences and Supersequences
• The Complexity of Downward Closure Comparisons
• The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
• The complexity of regular abstractions of one-counter languages
• Scattered Factor-Universality of Words
• General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
• Separability by piecewise testable languages and downward closures beyond subwords
• Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable
• On Arch Factorization and Subword Universality for Words and Compressed Words

This page was built for publication: Existential Definability over the Subword Ordering