STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA

DOI10.1142/S0129054107005443zbMath1183.68354OpenAlexW2168854371MaRDI QIDQ3401489

Paul Schofield, Kai Salomaa

Publication date: 29 January 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054107005443

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ State Complexity of Prefix Distance ⋮ Weak inverse neighborhoods of languages ⋮ State Complexity of Neighbourhoods and Approximate Pattern Matching ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Descriptional Complexity of Error Detection ⋮ Input-driven pushdown automata for edit distance neighborhood ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Quasi-Distances and Weighted Finite Automata ⋮ State complexity of prefix distance

Cites Work

• Unnamed Item
• Fast string correction with Levenshtein automata
• How hard is computing the edit distance?
• Finite Automata Computing Real Functions
• Order- n correction for regular languages

This page was built for publication: STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA