History Dependent Automata for Service Compatibility