Abstrakt. Redigeringsavståndet (eller Levenshteinavståndet) mellan två ord är det minsta antalet substitutioner, tillägg och raderingar av symboler som kan användas för att omvandla det ena ordet till det andra. I detta dokument överväger vi problemet med att beräkna redigeringsavståndet för ett vanligt språk (även känt som begränsningssystem), det vill säga den uppsättning ord som accepteras av en given ändlig automaton. Denna mängd är det minsta redigeringsavståndet mellan varje par distinkta ord i språket. Vi visar att problemet är polynomisk tids komplexitet. Vi skiljer två fall beroende på om den givna automaten är deterministisk eller icke-deterministisk. I det senare fallet är tids komplexiteten högre. För övrigt får vi också en övre gräns på redigeringsavståndet för ett vanligt språk i termer av automaton acceptera språket.
Problemet med att beräkna det minsta redigeringsavståndet mellan ett par olika strängar på ett vanligt språk har studerats i REF.
Computing the edit distance of a regular language
{'venue': 'in Proc. of IEEE Information Theory Workshop on Coding and Complexity, Roturoa, New Zealand, Aug. 29', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}