tailieunhanh - Applications of the finite state automata for counting restricted permutations and variations
In this paper, we use the finite state automata to count the number of restricted permutations and the number of restricted variations. For each type of restricted permutations, we construct a finite state automaton able to recognize and enumerate them. We, also, discuss how it encompasses the other known methods for enumerating permutations with restricted position, and in one case, we establish connections with some other combinatorial structures, such as subsets and compositions. | Yugoslav Journal of Operations Research 22 (2012), Number 2, 183-198 DOI: APPLICATIONS OF THE FINITE STATE AUTOMATA FOR COUNTING RESTRICTED PERMUTATIONS AND VARIATIONS Vladimir BALTIĆ Faculty of Organizational Sciences, University of Belgrade, Belgrade, Serbia baltic@ Received: February 2012 / Accepted: September 2012 Abstract: In this paper, we use the finite state automata to count the number of restricted permutations and the number of restricted variations. For each type of restricted permutations, we construct a finite state automaton able to recognize and enumerate them. We, also, discuss how it encompasses the other known methods for enumerating permutations with restricted position, and in one case, we establish connections with some other combinatorial structures, such as subsets and compositions. Keywords: Finite state automata, restricted permutations, restricted variations, exact enumeration. MSC: 11B85, 05A15, 05A05, 11B39. 1. INTRODUCTION For the beginning, we give the concepts of the finite state automaton, restricted permutations and restricted variations. A finite state automaton M consists of five parts: 1. a finite set (alphabet) T of inputs; 2. a finite set S of (internal) states; 3. a subset Y of S (whose elements are called final, accepting or “yes” states); 4. an initial state (or start state) s0 in S ; 5. a next-state function F from S × T into S . Such an automaton M is denoted by: M = (T , S , Y , s0 , F ) . V. Baltić / Applications of the Finite State Automata for Counting 184 A state is said to be accessible state if it can be reached from the start state. A state s ∈ S is called sink state if f ( s, x) = s for all x ∈ T . The nondeterministic finite automaton is a variant of finite automaton with the following characteristic: zero or more than one possible value may exist for state transition (in the deterministic finite automaton, the next possible state is uniquely determined). More about .
đang nạp các trang xem trước
