Abstract Markov kedjor är ett välkänt verktyg för att modellera tidsmässiga egenskaper hos många fenomen, från textstruktur till fluktuationer i ekonomi. Eftersom de är lätta att generera, Markovian sekvenser, dvs.. temporal sekvenser som har Markov egenskap, används också för innehållsgenerering program som text eller musik generation som imiterar en viss stil. Men Markov sekvenser genereras traditionellt med hjälp av giriga, vänster-till-höger algoritmer. Även om detta tillvägagångssätt är beräknings billigt, är det i grunden olämpligt för interaktiv kontroll. I detta dokument behandlas frågan om att generera styrbara Markoviska sekvenser. Vi riktar interaktiva program som spel, där användare vill styra, genom enkla inmatningsenheter, hur systemet genererar en markoviansk sekvens, såsom en text, en musikalisk sekvens eller en ritning. För att nå detta mål föreslår vi att Markovs sekvensgenerering ses över som en gren och ett problem med begränsad tillfredsställelse (CSP). Vi föreslår en CSP-formulering av den grundläggande Markoviska hypotesen som elementära Markov Constraints (EMC). Vi föreslår algoritmer som uppnår domänkonsistens för EMC:s propagatorer, i ett händelsebaserat genomförande av CSP. Vi visar hur EMC kan kombineras för att uppskatta den globala Markoviska sannolikheten för en hel sekvens, och rymma för olika arter av Markov generation såsom fast ordning, variabel ordning, eller utjämning. En sådan formulering, även om den är dyrare än traditionella giriga generationsalgoritmer, ger den enorma fördelen av att vara naturligt styrbar, eftersom kontrollspecifikationer kan representeras av godtyckliga ytterligare begränsningar, utan någon ändring av generationsalgoritmen. Vi illustrerar vår strategi på enkla men ändå kombinatoriska ackord sekvens och melodi generation problem och ge några resultat.
REF, t.ex., använder begränsningar i en sådan musikgenereringsprocess.
Markov constraints: steerable generation of Markov sequences
{'venue': 'Constraints', 'journal': 'Constraints', 'mag_field_of_study': ['Computer Science', 'Mathematics']}