Vi introducerar strömmande datastränggivare som kartindatasträngar till utgående datasträngar i ett enda vänster-till-höger pass i linjär tid. Datasträngar är (obundna) sekvenser av datavärden, taggade med symboler från en ändlig uppsättning, över en potentiellt oändlig datadomän som stöder endast verksamheten av jämlikhet och beställning. Givaren använder en ändlig uppsättning tillstånd, en ändlig uppsättning variabler som sträcker sig över datadomänen, och en ändlig uppsättning variabler som sträcker sig över datasträngar. I varje steg kan den fatta beslut baserat på nästa inmatningssymbol, uppdatera sitt tillstånd, komma ihåg inmatningsvärdet i sina datavariabler, och uppdatera datasträngsvariabler genom att sammanbinda datasträngsvariabler och nya symboler som bildas från datavariabler, samtidigt som dubblering undviks. Vi konstaterar att problemen med att kontrollera funktionell likvärdighet av två strömmande givare, och att kontrollera om en streaming givare uppfyller pre / post verifiering villkor som anges av streaming acceptorer över inmatning/utmatning data-strängar, finns i PSPACE. Vi identifierar en klass av imperativ och en klass av funktionella program, manipulera listor över dataobjekt, som effektivt kan översättas till strömmande data-sträng givare. De imperativ program dynamiskt modifiera en ensam länkad hög genom att ändra nästa pekare av heap-nodes och genom att lägga till nya noder. Den huvudsakliga begränsningen anger hur nästa pekare kan användas för traversal. Vi identifierar också ett uttrycksfullt likvärdigt fragment av funktionella program som passerar en lista med syntaktiskt begränsade rekursiva samtal. Våra resultat leder till algoritmer för att kontrollera påståenden och för att kontrollera funktionell ekvivalens av två program, eventuellt skrivna i olika programmeringsstilar, för vanliga rutiner som infoga, ta bort och vända.
Arbetet i REF minskar bekräfta kontroll av enkel-pass list-behandlingsprogram till frågor om datastränggivare som arbetar över sekvenser av taggade datavärden.
Streaming transducers for algorithmic verification of single-pass list-processing programs
{'venue': "POPL '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}