On the structure of systematic prefix codes

Systematic prefix codes play an important role in coding theory, we relate them with the problem of the partition of a free (sub-) monoid into two free sub-monoids. We show too that among the dual codes of a systematic prefix code A there exists one and only one which appears in the automaton recognizing A ^*. The characterization of this automaton and some corollaries stated here will allow us to show in further note that systematic prefix codes are involved in the structure of any regular prefix code. Work done under CNR contract No. R-l7-02-417-0-A.     

On input semigroups of automata

In this paper, we consider the problem of what topological semigroups can serve as input semigroups of what (topological) automata. A semigroup is said to be admissible if it serves as an input semigroup of a non-trivial strongly connected automaton that has a distinguishable state (see Definition 2). For the discrete or the compact case, the class of all the admissible semigroups is fully characterized: a discrete or compact topological semigroup (I, m) is admissible if and only if there exists a closed congruence relationR such that the quotient semigroup (I/R, m _R ) is non-trivial, right simple, and left unital. This work stems from Weeg's [10], who considered a similar problem in the discrete case.In the last section of the paper, a conjecture of Weeg [10, p. 264] is resolved in the negative.     

On regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

On the structure of binary feedforward inverses with delay 2

Let M‘=S(Mα,f)be a semi-input-memory finite automaton with input alphabet Y and output alphabet X.If X=Y={0,1},then M‘ is a feedforware inverse with delay 2 if and only if there exists a cycle c of state diagram of Mαsuch that f(y0,…,yc,λα（t)0 can be expressed in the form of f ^(1)(y0,…,yc-1,λα（t)) yc for any state t in C and y0,y1,…,yc in Y;or of f^(2)(y0,…,yc-2,λα（t)) yc-c for any state t in Cand y0,y1,…,yc in Y;or for any state t in Cand y0,y1,…yc,in Y,y0,y1…yc satisfies the D[t] condition.The socalled y0,y1…yc satisfying the D[t] condition is that:for some i,j,(i,j)∈{(1,2),(1,3),(2,1),(2,2),(3,1),(3,2)},there exists a (c 2-k)-ary function f^(k),k=1,2,3,such that the Equation(1)and Equation (2)hokl simultaneously for all y‘c-2,…,y‘c 1∈Y. Equation (1);f(y0,…,yc-i,y‘c-i 1,…y‘c,λα（t))=f^(j)(y0,…yc-i,λα（t）） y‘c-i 1 Equation (2):f(y1,…,yc-j 1,y‘c-j 2,…,y‘c 1,λα（t））=f^(j)(y1,…,yc-j 1,λα（t）） y‘c-j s where t=δα（t）and if (i,j)=(1,2)then one and only one of the following conditions C1 and C2 holds for all y‘c-1,y‘c,y‘c 1∈Y.Condition C1:there exists a c-ary function g^(1),such that f(y0,…,yc-2,y‘c-1,y‘c,λα（t））=g^(1),(y0,…,yc-2,λα（t）） y‘c-1( )y‘c;Condition C2:there exists a (c-1)-ary functiong g^(2)such that f(y1,…,yc-2,y‘c-1,y‘c,y‘c 1,λα（t））=g^(2)(y1,…,yc-2,λα（t）） y‘c-1 y‘c,where t=δα(t).     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Finite canonical rewriting systems for congruences generated by concurrency relations

WhenC is a concurrency relation on alphabet , then ^*/= _C is a free partially commutative monoid. Here we show that it is decidable in polynomial time whether or not there exists a finite canonical rewriting systemR on such that the congruences _R ^* generated byR and = _C induced byC coincide. Further, in case such a systemR exists, one such system can be determined in polynomial time.     

On closure properties of bounded two-sided error complexity classes

We show that if a complexity classC is closed downward under polynomial-time majority truth-table reductions ( _mtt ^p ), then practically every other polynomial closure property it enjoys is inherited by the corresponding bounded two-sided error class BP[C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practically every closure property of NP. Our main lemma shows that, for any relativizable classD which meets two fairly transparent technical conditions, we haveC ^BP[C] BP[D ^C]. Among our applications, we simplify the proof by Toda [Tol], [To2] that the polynomial hierarchy PH is contained in BP[P]. We also show that relative to a random oracleR, PH ^R is properly contained in P ^R .The first author was supported in part by NSF Grant CCR-9011248 and the second author was supported in part by NSF Grant CCR-89011154.     

Strong Minimax Lower Bounds for Learning

Minimax lower bounds for concept learning state, for example, that for each sample size n and learning rule g _n , there exists a distribution of the observation X and a concept C to be learnt such that the expected error of g _n is at least a constant times V/n, where V is the vc dimension of the concept class. However, these bounds do not tell anything about the rate of decrease of the error for a fixed distribution-concept pair.In this paper we investigate minimax lower bounds in such a (stronger) sense. We show that for several natural k-parameter concept classes, including the class of linear halfspaces, the class of balls, the class of polyhedra with a certain number of faces, and a class of neural networks, for any sequence of learning rules {g _n }, there exists a fixed distribution of X and a fixed conceptC such that the expected error is larger than a constant timesk/n for infinitely many n. We also obtain such strong minimax lower bounds for the tail distribution of the probability of error, which extend the corresponding minimax lower bounds.     

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.     

Fast periodic graph exploration with constant memory

We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a robot. The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor coloured. However, while visiting a node v the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers 1,…,d(v) called port numbers, where d(v) is the degree of v. Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. In this paper, we are interested in minimisation of the length of the exploration period. In other words, we want to minimise the maximum number of edge traversals performed by the robot between two consecutive visits of a generic node, in the same state and entering the node by the same port. Note that the problem is unsolvable if the local port numbers are set arbitrarily, see [L. Budach, Automata and labyrinths, Math. Nachr. 86 (1978) 195–282]. In this context, we are looking for the minimum function π(n), such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size n along a traversal route with the period π(n). Dobrev et al. proved in [S. Dobrev, J. Jansson, K. Sadakane, W.-K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: Proc. 12th Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, in: Lecture Notes in Comput. Sci., vol. 3499, Springer, Berlin, 2005, pp. 127–139] that for oblivious robots π(n)10n. Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [D. Ilcinkas, Setting port numbers for fast graph exploration, in: Proc. 13th Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, in: Lecture Notes in Comput. Sci., vol. 4056, Springer, Berlin, 2006, pp. 59–69], where the exploration period π(n)4n−2. In the same paper, it is conjectured that the bound 4n−O(1) is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in π(n)<3.75n−2 steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of π(n)2n−2 holding for any robot.     

On weak isometries of Preparata codes

Two codes C ₁ and C ₂ are said to be weakly isometric if there exists a mapping J: C ₁ → C ₂ such that for all x, y in C ₁ the equality d(x, y) = d holds if and only if d(J(x), J(y)) = d, where d is the code distance of C ₁. We prove that Preparata codes of length n ≥ 2¹² are weakly isometric if and only if the codes are equivalent. A similar result is proved for punctured Preparata codes of length at least 2¹⁰ ? 1.     

A cellular automaton for blocking queen games

We show that the winning positions of a certain type of two-player game form interesting patterns which often defy analysis, yet can be computed by a cellular automaton. The game, known as Blocking Wythoff Nim, consists of moving a queen as in chess, but always towards (0, 0), and it may not be moved to any of \(k-1\) temporarily “blocked” positions specified on the previous turn by the other player. The game ends when a player wins by blocking all possible moves of the other player. The value of k is a parameter that defines the game, and the pattern of winning positions can be very sensitive to k. As k becomes large, parts of the pattern of winning positions converge to recurring chaotic patterns that are independent of k. The patterns for large k display an unprecedented amount of self-organization at many scales, and here we attempt to describe the self-organized structure that appears. This paper extends a previous study (Cook et al. in Cellular automata and discrete complex systems, AUTOMATA 2015, Lecture Notes in Computer Science, vol 9099, pp 71–84, 2015), containing further analysis and new insights into the long term behaviour and structures generated by our blocking queen cellular automaton.     

Collective Tree Spanners in Graphs with Bounded Parameters

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system $\mathcal{T}(G)In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system T(G)\mathcal{T}(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ? T(G)T\in\mathcal{T}(G) exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of O(?n)O(\sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree (2w)(2\mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree (2?c/2?w)(2\lfloor c/2\rfloor\mathsf{w}) -spanners and a system of 4log ₂ n collective additive tree (2(?c/3?+1)w)(2(\lfloor c/3\rfloor +1)\mathsf {w}) -spanners (here, w\mathsf{w} is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree (2w)(2\mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.     

Crown graphs and subdivision of ladders are odd graceful

A graph G of size q is odd graceful, if there is an injection φ from V(G) to {0, 1, 2, …, 2q?1} such that, when each edge xy is assigned the label or weight |f(x)?f(y)|, the resulting edge labels are {1, 3, 5, …, 2q?1}. This definition was introduced in 1991 by Gnanajothi [3], who proved that the graphs obtained by joining a single pendant edge to each vertex of C _n are odd graceful, if n is even. In this paper, we generalize Gnanajothi's result on cycles by showing that the graphs obtained by joining m pendant edges to each vertex of C _n are odd graceful if n is even. We also prove that the subdivision of ladders S(L _n ) (the graphs obtained by subdividing every edge of L _n exactly once) is odd graceful.     

On the finite degree of ambiguity of finite tree automata

Summary The degree of ambiguity of a finite tree automaton A, da(A), is the maximal number of different accepting computations of A for any possible input tree. We show: it can be decided in polynomial time whether or not da(A)<. We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton A with n states and rank L>1 having a finite degree of ambiguity: for every input tree t there is a input tree t ₁ of depth less than 2²ⁿ·n! having the same number of accepting computations; the degree of ambiguity of A is bounded by 2^{2 2·log(L+1)·n}.     

Electric S-brane solutions corresponding to rank-2 Lie algebras: Acceleration and small variation of <Emphasis Type="Italic">G</Emphasis>

Electric S-brane solutions with two non-composite electric branes and a set of l scalar fields are considered. The intersection rules for branes correspond to Lie algebras A ₂, C ₂ and G ₂. The solutions contain five factor spaces. One of them, M ₀, is interpreted as our 3-dimensional space. It is shown that there exists a time interval where accelerated expansion of our 3-dimensional space is compatible with a small enough variation of the effective gravitational constant G(τ). This interval contains τ ₀, a point of minimum of the function G(τ). A special solution with two phantom scalar fields is analyzed, and it is shown that, in the vicinity of the point τ ₀, the time variation of G(τ) (calculated in the linear approximation) decreases in the sequence of Lie algebras A ₂, C ₂ and G ₂.     

Two-way automata and length-preserving homomorphisms

Closure underlength-preserving homomorphisms is interesting because of its similarity tonondeterminism. We give a characterization of NP in terms of length-preserving homomorphisms and present related complexity results. However, we mostly study the case of two-way finite automata: Let l.p.hom[n state 2DFA] denote the class of languages that are length-preserving homomorphic images of languages recognized byn-state 2DFAs. We give a machine characterization of this class. We show that any language accepted by ann-state two-wayalternating finite automaton (2AFA), or by a l-pebble 2NFA, belongs to l.p.hom[O(n ²) state 2DFA]. Moreover, there are languages in l.p.hom[n state 2DFA] whose smallest accepting 2NFA has at leastc ⁿ states (for some constantc > 1). So for two-way finite automata, the closure under length-preserving homomorphisms is much more powerful than nondeterminism. We disprove two conjectures (of Meyer and Fischer, and of Chrobak) about the state-complexity of unary languages. Finally, we show that the equivalence problems for 2AFAs (resp. 1-pebble 2NFAs) are in PSPACE, and that the equivalence problem for 1-pebble 2AFAs is in ExpSPACE (thus answering a question of Jiang and Ravikumar); it was known that these problems are hard in these two classes. We also give a new proof that alternating 1-pebble machines recognize only regular languages (which was first proved by Goralčíket al.). This research was supported in part by N.S.F. Grant DMS 8702019.     

Congruence separation of subsets of a monoid with applications to automata

LetF be a monoid and letA={A _i iI} be a set of disjoint subsets ofF, whereI is an index set. A congruence onF is calledA-separating if each of its congruence classes has a non-empty intersection with at most one A_i A The setC ^A of allA-separating congruences onF is a lower semi-lattice with respect to the partial ordering of congruence inclusion. A necessary and sufficient condition forC ^A to be a complete lattice is derived and, in that case, the unique maximalA-separating congruence is characterized. The relation ofA-separating congruences with automata is described. An example of the case that the unique maximalA-separating congruence on a free monoid exists is worked out, and its realization by an incompletely specified finite automaton is given.     

On some applications of Ruscheweyh derivative

In this paper, we discuss a subclass V_k(β,b,δ) of analytic functions, which was introduced and discussed by Latha and Nanjunda Rao (1994) [3]. Some results such as inclusion relationship, coefficient inequality and radius of convexity for this class are proved. We also observe that this class is preserved under the Bernardi integral transform.