Vi föreslår en deterministisk modell för att koppla samman kostnader med strängar som är parameteriserade av verksamheter av intresse (såsom tillägg, skalning, och minimum), ett begrepp om regelbundenhet som ger en måttstock för att mäta expressivitet, och studera beslutsproblem och teoretiska egenskaper av resulterande klasser av kostnadsfunktioner. Vår definition av regelbundenhet bygger på teorin om string-to-tree givare, och gör det möjligt att associera kostnader med händelser som är beroende av regelbundna egenskaper av framtida händelser. Vår modell av kostnadsregisterautomata möjliggör beräkning av regelbundna funktioner med hjälp av flera "skrivbara" register vars värden kan kombineras med den tillåtna uppsättningen av operationer. Vi visar att de klassiska kortaste algoritmerna samt algoritmerna för beräkning av rabatterade kostnader kan anpassas för att lösa min-kostnadsproblemen för de mer allmänna kategorierna av funktioner som specificeras i vår modell. Cost register automata med verksamheten som minimum och ökning ger en deterministisk modell som är likvärdig med viktad automata, en omfattande studerat icke-deterministisk modell, och detta samband resulterar i nya insikter och nya öppna problem.
En annan relaterad modell för att specificera kvantitativa egenskaper är kostnadsregister automata (CRA) REF ), som parametriseras av kostnadsfunktioner.
Regular Functions and Cost Register Automata
{'venue': '2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science', 'journal': '2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science', 'mag_field_of_study': ['Computer Science']}