Abstrakt. Problemet med att beräkna redigeringsavståndet mellan en sträng och en ändlig automaton uppstår i en mängd olika tillämpningar inom beräkningsbiologi, textbehandling och taligenkänning. I detta dokument presenteras linjära rymdalgoritmer för beräkning av redigeringsavståndet mellan en sträng och en godtycklig vägd automaton över den tropiska semiringen, eller en otvetydig vägd automaton över en godtycklig semiring. Det ger också en effektiv linjär-rymd algoritm för att hitta en optimal anpassning av en sträng och en sådan viktad automaton.
En platseffektiv algoritm för att beräkna redigeringsavståndet mellan en sträng och en viktad automaton över en tropisk semiring utvecklades i REF.
Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}