作者: Margus Veanes , Loris D’Antoni
DOI: 10.1007/S10703-015-0233-4
关键词:
摘要: Symbolic finite automata and transducers augment classic with symbolic alphabets represented as parametric theories. This extension enables to succinctly represent large potentially infinite while preserving closure decidability properties. Extended further extend these objects by allowing transitions read consecutive input elements in a single step. In this paper we study the properties of models. contrast case alphabets, show how reading multiple symbols increases expressiveness models, which causes some stop holding most decision problems become undecidable. particular extended are not closed under composition, equivalence problem is undecidable for both transducers. We then introduce subclass Cartesian guards limited conjunctions unary predicates propose an algorithm single-valued case. also present heuristic composing that works many practical cases. Finally, model real world programs use proposed algorithms prove their correctness.