In this paper we introduce a class of descriptors for regular languages arising from an application of the Stone duality between finite Boolean algebras and finite sets. These descriptors, called classical fortresses, are object specified in classical propositional logic and capable to accept exactly regular languages. To prove this, we show that the languages accepted by classical fortresses and deterministic finite automata coincide. Classical fortresses, besides being propositional descriptors for regular languages, also turn out to be an efficient tool for providing alternative and intuitive proofs for the closure properties of regular languages.
A Logical Descriptor for Regular Languages via Stone Duality / S. Aguzzoli, D. Diaconescu, T. Flaminio - In: Theoretical Aspects of Computing – ICTAC 2014 / [a cura di] G. Ciobanu, D. Méry. - [s.l] : Springer International Publishing, 2014. - ISBN 978-3-319-10881-0. - pp. 25-42 (( Intervento presentato al 11. convegno ICTAC tenutosi a Bucharest nel 2014 [10.1007/978-3-319-10882-7_3].
A Logical Descriptor for Regular Languages via Stone Duality
S. AguzzoliPrimo
;
2014
Abstract
In this paper we introduce a class of descriptors for regular languages arising from an application of the Stone duality between finite Boolean algebras and finite sets. These descriptors, called classical fortresses, are object specified in classical propositional logic and capable to accept exactly regular languages. To prove this, we show that the languages accepted by classical fortresses and deterministic finite automata coincide. Classical fortresses, besides being propositional descriptors for regular languages, also turn out to be an efficient tool for providing alternative and intuitive proofs for the closure properties of regular languages.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
