Search results for "code"
showing 10 items of 1180 documents
A new Euler–Mahonian constructive bijection
2011
AbstractUsing generating functions, MacMahon proved in 1916 the remarkable fact that the major index has the same distribution as the inversion number for multiset permutations, and in 1968 Foata gave a constructive bijection proving MacMahon’s result. Since then, many refinements have been derived, consisting of adding new constraints or new statistics.Here we give a new simple constructive bijection between the set of permutations with a given number of inversions and those with a given major index. We introduce a new statistic, mix, related to the Lehmer code, and using our new bijection we show that the bistatistic (mix,INV) is Euler–Mahonian. Finally, we introduce the McMahon code for …
A loopless algorithm for generating the permutations of a multiset
2003
AbstractMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.
The structure of the state representation of shift invariant controllable and observable group codes
2000
AbstractIn this paper an investigation on the structure of the canonical trellis section of shift invariant, l-controllable and m-observable group codes is carried out. Necessary and sufficient conditions for a set of group homomorphisms in order that they represent the trellis section of this class of codes are established.
A fractal set from the binary reflected Gray code
2005
The permutation associated with the decimal expression of the binary reflected Gray code with $N$ bits is considered. Its cycle structure is studied. Considered as a set of points, its self-similarity is pointed out. As a fractal, it is shown to be the attractor of a IFS. For large values of $N$ the set is examined from the point of view of time series analysis
On the size of transducers for bidirectional decoding of prefix codes
2012
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation wi…
Loop-free Gray code algorithm for the e-restricted growth functions
2011
The subject of Gray codes algorithms for the set partitions of {1,2,...,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of [email protected]?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,...,n}, Ruskey and Savage (1994) [9] generalized [email protected]?s results and give two Gray codes for the set of partitions of {1,2,...,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques. In this paper, we introduce the set of e-restricte…
A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers asso…
Equations on trees
1996
We introduce the notion of equation on trees, generalizing the corresponding notion for words, and we develop the first steps of a theory of tree equations. The main result of the paper states that, if a pair of trees is the solution of a tree equation with two indeterminates, then the two trees are both powers of the same tree. As an application, we show that a tree can be expressed in a unique way as a power of a primitive tree. This extends a basic result of combinatorics on words to trees. Some open problems are finally proposed.
Real-space grids and the Octopus code as tools for the development of new simulation approaches for electronic systems.
2015
This Open Access Article is licensed under a Creative Commons Attribution 3.0 Unported Licence.
Semantics for Managing Systems in Heterogeneous and Distributed Environment
2002
The problem of legacy systems collaboration is being solved. Particularly we look at the collaboration as workflow in a distributed and heterogeneous environment. Attention is paid to the description of semantics for workflow process definition languages. There are many solutions how semantics can be decomposed into logical fragments, but the problem of obtaining reusable components that are easy to compile into desired specific semantics still remains. We evolve the division of semantics by semantic aspects whose description is based on abstract data types (pre-built components) and connectors (meta-programs to produce the glue code) between them. This paper offers a way in which semantic …