Input-driven pushdown automata for edit distance neighborhood

DOI10.1016/j.tcs.2022.03.024OpenAlexW4220920985MaRDI QIDQ5918675

Alexander Szabari, Viliam Geffert, Zuzana Bednárová

Publication date: 10 May 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.03.024

zbMATH Keywords

context-free languagesedit distanceinput-driven pushdown automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
• Intersection and union of regular languages and state complexity
• How hard is computing the edit distance?
• The relative edit-distance between two input-driven languages
• Edit-Distance Between Visibly Pushdown Languages
• STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
• Adding nesting structure to words
• Visibly pushdown languages
• The String-to-String Correction Problem
• State Complexity of Neighbourhoods and Approximate Pattern Matching
• Syntax-directed least-errors analysis for context-free languages
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• Near-optimal, single-synchronization-error-correcting code
• Spelling correction in systems programs
• A Minimum Distance Error-Correcting Parser for Context-Free Languages
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• Further closure properties of input-driven pushdown automata
• Edit distance neighbourhoods of input-driven pushdown automata
• Edit distance neighbourhoods of input-driven pushdown automata

This page was built for publication: Input-driven pushdown automata for edit distance neighborhood