A Logical Descriptor for Regular Languages via Stone Duality

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] 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) | Request a copy

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:

10 Sep 2015 10:42

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 Edit item
Provide Feedback