Balancedness of MSO transductions in polynomial time.
Sebastian ManethHelmut SeidlPublished in: Inf. Process. Lett. (2018)
Keyphrases
- finite state
- finite automata
- regular expressions
- finite state transducers
- tree automata
- markov chain
- special case
- markov decision processes
- monadic second order logic
- model checking
- pattern matching
- bounded treewidth
- expressive power
- machine translation
- xml schema
- language modeling
- approximation algorithms
- machine learning
- computational complexity
- search algorithm