Diaconescu, Denisa; Aguzzoli, Stefano; Flaminio, Tommaso (2014). A Logical Descriptor for Regular Languages via Stone Duality. In: Ciobanu, Gabriel; Méry, Dominique (eds.) Theoretical Aspects of Computing – ICTAC 2014. 11th International Colloquium, Bucharest, Romania, September 17-19, 2014. Proceedings. Lecture Notes in Computer Science: Vol. 8687 (pp. 25-42). Cham: Springer 10.1007/978-3-319-10882-7_3
![[img]](https://boris.unibe.ch/style/images/fileicons/text.png) |
Text
chp%3A10.1007%2F978-3-319-10882-7_3.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (314kB) |
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.
Item Type: |
Book Section (Book Chapter) |
|---|---|
Division/Institute: |
08 Faculty of Science > Department of Mathematics and Statistics > Institute of Mathematics |
UniBE Contributor: |
Diaconescu, Denisa |
Subjects: |
500 Science > 510 Mathematics |
ISBN: |
978-3-319-10881-0 |
Series: |
Lecture Notes in Computer Science |
Publisher: |
Springer |
Language: |
English |
Submitter: |
George Metcalfe |
Date Deposited: |
19 Mar 2015 12:50 |
Last Modified: |
05 Dec 2022 14:44 |
Publisher DOI: |
10.1007/978-3-319-10882-7_3 |
BORIS DOI: |
10.7892/boris.65221 |
URI: |
https://boris.unibe.ch/id/eprint/65221 |
Actions (login required)
 |
Edit item |