In the XML standard, data are represented as unranked labeled ordered trees. Regular unranked tree automata provide a useful formalism for the validation of schemas enforcing regular structural constraints on XML documents. However some concrete application contexts need the expression of more general constraints than the regular ones. In this paper we propose a new framework in which context-free style structural constraints can be expressed and validated. This framework is characterized by: (i)...

A new proof of Maxfield’s theorem is given, using automata and results from Symbolic Dynamics. These techniques permit to prove that points that are near normality to base $p^k$ (resp. $p$) are also near normality to base $p$ (resp. $p^k$), and to study genericity preservation for non Lebesgue measures when going from one base to the other. Finally, similar results are proved to bases the golden mean and its square.

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the probabilistic case of Chrobak normal form, obtained...

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...

We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret....

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\left\{L_m\right\}$ of cyclic languages, where $L_m=\left\{a^{km}\right|k\in \mathbb{N}\}$. In particular, we show that, for any $m$, the number of states necessary and sufficient for accepting the unary language $L_m$ with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of $m$. To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on...

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {Lm} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages...