Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, we give and analyze an algorithm for the efficient construction of deterministic finite automata (DFA) designed to operate directly on tokenizations produced by the popular byte pair encoding (BPE) technique. This makes it possible to apply many existing techniques and algorithms to the tokenized case, such as pattern matching, equivalence checking of tokenization dictionaries, and composing tokenized languages in various ways. The construction preserves some key properties of the automaton, and we use this to establish asymptotic bounds on the state complexity of the automata that result. Finally, we demonstrate how to construct an input-deterministic (subsequential) string-to-string transducer which precisely describes the relationship between strings and their correct tokenizations.

Current dynamic analysis tools for Android applications do not get good code coverage since they can only explore a subset of the behaviors of the applications and do not have full control over the environment in which they execute. In this work we use model checking to systematically explore application paths while reducing the analysis size using state matching and backtracking. In particular, we extend the Java PathFinder (JPF) model checking environment for Android. We describe the difficulties one needs to overcome to make this a reality as well as our current approaches to handling these issues. We obtain significantly higher coverage using shorter event sequences on a representative sample of Android apps, when compared to Dynodroid and Sapienz, the current state-of-the-art dynamic analysis tools for Android applications.

We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary conc atenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n–1)·m+n states, otherwise, on DFAs accepting the cut of two individual languages that are accepted by n- and m-state DFAs, respectively. In the unary case we obtain max(2n–1,m+n–2) states as a tight bound—notice that for m ≤ n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1) · F(1,n+2,–n+2;n+1 | –1) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n – 1)!). Finally, the bound drops to 2n – 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.