scientific article; zbMATH DE number 7297889

zbMath1452.03028arXiv1701.07470MaRDI QIDQ5144688

Georg Zetzsche, Simon Halfon, Philippe Schnoebelen

Publication date: 19 January 2021

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Scattered Factor-Universality of Words ⋮ The Subtrace Order and Counting First-Order Logic ⋮ Word equations in the context of string solving ⋮ Complexity in Young's lattice ⋮ Absent Subsequences in Words ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Ranking and Unranking k-Subsequence Universal Words ⋮ Longest Common Subsequence with Gap Constraints ⋮ On Arch Factorization and Subword Universality for Words and Compressed Words ⋮ Alternating complexity of counting first-order logic for the subword order ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Existential Definability over the Subword Ordering ⋮ Absent subsequences in words ⋮ First-order concatenation theory with bounded quantifiers ⋮ On shuffle products, acyclic automata and piecewise-testable languages ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: