Risks and potentials of using EMV for internet payments
Els van Herreweghen, Uta Wille
USENIX Workshop on Smartcard Technology 1999
Alternation is a generalization of nondeterminism in which existential and universal quantitiers can alternate during the course of a computation, whereas in a nondeterministic computation there are only existential quantifiers. Alternating Turing machines are defined and shown to accept precisely the recursively enumerable sets. Complexity classes of languages accepted by time- (space-) bounded alternating Turing machines are characterized in terms of complexity classes of languages accepted by space- (time-) bounded deterministic Turing machines. In particular, alternating polynomial time is equivalent to deterministic polynomial space and alternating polynomial space is equivalent to deterministic ‘exponential time. Subrecursive quantifier hierarchies are defined in terms of time- or space-bounded alternating Tufing machines by bounding the number of alternations allowed during computations. Alternating finite-state automata are defined and shown to accept only regular languages, although, in general, 2 2 states are necessary and sufficient to simulate a k-state alternating finite automaton deterministically. Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata. © 1981, ACM. All rights reserved.
Els van Herreweghen, Uta Wille
USENIX Workshop on Smartcard Technology 1999
Amarachi Blessing Mbakwe, Joy Wu, et al.
NeurIPS 2023
Rei Odaira, Jose G. Castanos, et al.
IISWC 2013
Amy Lin, Sujit Roy, et al.
AGU 2024