A formal power series φ with a real cut point λ defines the language L_{φ,λ} = {ω ∈ Σ∗ | |φ(ω) > λ}; λ is called isolated if inf_ω |φ(ω) − λ| > 0. In this paper we give conditions for guaranteeing the regularity of L_{φ,λ}, with λ isolated, for two classes of formal series: rational series and Hadamard quotients of rational series. Finally, we provide an explicit representation of the behavior of a subclass of two-way weighted automata in terms of Hadamard quotient of rational series.
Regularity of languages defined by formal series with isolated cut point / A. Bertoni, M.P. Bianchi, F. D'Alessandro - In: Third workshop on non-classical models for automata and applications - NCMA 2011 : Milan, Italy, july 18-19, 2011 : proceedings / [a cura di] R. Freund, Markus Holzer, C. Mereghetti, F. Otto, B. Palano. - Vienna : Austrian Computer Society, 2011. - ISBN 9783854032823. - pp. 73-87 (( Intervento presentato al 3. convegno Workshop on Non-Classical Models for Auomata and Applications tenutosi a Milan, Italy nel 2011.
Regularity of languages defined by formal series with isolated cut point
A. Bertoni;M.P. Bianchi;
2011
Abstract
A formal power series φ with a real cut point λ defines the language L_{φ,λ} = {ω ∈ Σ∗ | |φ(ω) > λ}; λ is called isolated if inf_ω |φ(ω) − λ| > 0. In this paper we give conditions for guaranteeing the regularity of L_{φ,λ}, with λ isolated, for two classes of formal series: rational series and Hadamard quotients of rational series. Finally, we provide an explicit representation of the behavior of a subclass of two-way weighted automata in terms of Hadamard quotient of rational series.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
