Sublinear DTD Validity
From MaRDI portal
Publication:2799222
DOI10.1007/978-3-319-15579-1_58zbMath1451.68091OpenAlexW1875018304MaRDI QIDQ2799222
Joachim Niehren, Antoine Ndione, Aurélien Lemay
Publication date: 8 April 2016
Published in: Language and Automata Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-15579-1_58
Formal languages and automata (68Q45) Information storage and retrieval of data (68P20) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Approximate membership for regular languages modulo the edit distance
- \(\omega\)-regular languages are testable with a constant number of queries
- A relation between edit distance for ordered trees and edit distance for Euler strings
- The tree-to-tree editing problem
- Regular expressions into finite automata
- Regular Languages are Testable with a Constant Number of Queries
- Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
- Approximate Satisfiability and Equivalence
- Adding nesting structure to words
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Every property of hyperfinite graphs is testable
- Regular Expressions and NFAs Without ε-Transitions
This page was built for publication: Sublinear DTD Validity
