scientific article; zbMATH DE number 7056230
From MaRDI portal
Publication:5376657
zbMath1421.68063arXiv1511.01807MaRDI QIDQ5376657
Philippe Schnoebelen, Prateek Karandikar
Publication date: 17 May 2019
Full work available at URL: https://arxiv.org/abs/1511.01807
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Formal languages and automata (68Q45) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)
Related Items (15)
Scattered Factor-Universality of Words ⋮ The Subtrace Order and Counting First-Order Logic ⋮ Unnamed Item ⋮ Absent Subsequences in Words ⋮ 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 ⋮ Unnamed Item ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence ⋮ Unnamed Item ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the state complexity of reversals of regular languages
- Piecewise testable languages via combinatorics on words
- On the state complexity of closures and interiors of regular languages with subwords and superwords
- Kernel methods for learning languages
- Definability in substructure orderings. I: Finite semilattices
- Partially ordered finite monoids and a theorem of I. Simon
- Classification of finite monoids: the language approach
- Polynomial closure and unambiguous product
- Simon's theorem for scattered words
- On shuffle products, acyclic automata and piecewise-testable languages
- On Boolean combinations forming piecewise testable languages
- On the index of Simon's congruence for piecewise testability
- Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
- Piecewise testable tree languages
- Recompression
- Theories of orders on the set of words
- An Approach to Computing Downward Closures
- On the Complexity of k-Piecewise Testability and the Depth of Automata
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Definability in the Subword Order
- Satisfiability of word equations with constants is in PSPACE
- Deciding Piecewise Testable Separability for Regular Tree Languages
- Separability by piecewise testable languages and downward closures beyond subwords
- The Height of Piecewise-Testable Languages with Applications in Logical Complexity
- Alternative Automata Characterization of Piecewise Testable Languages
- Cognitive and Sub-regular Complexity
- On free monoids partially ordered by embedding
- Ordering by Divisibility in Abstract Algebras
This page was built for publication:
