Boolean Automata and Atoms of Regular Languages

Autor:	Tamm, Hellis
Jazyk:	angličtina
Rok vydání:	2021
Předmět:	Atoms TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Theory of computation → Formal languages and automata theory Regular language Boolean automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Computer Science::Formal Languages and Automata Theory
DOI:	10.4230/lipics.mfcs.2021.86
Popis:	We examine the role that atoms of regular languages play in boolean automata. We observe that the size of a minimal boolean automaton of a regular language is directly related to the number of atoms of the language. We present a method to construct minimal boolean automata, using the atoms of a given regular language. The "illegal" cover problem of the Kameda-Weiner method for NFA minimization implies that using the union operation only to construct an automaton from a cover - as is the case with NFAs -, is not sufficient. We show that by using the union and the intersection operations (without the complementation operation), it is possible to construct boolean automata accepting a given language, for a given maximal cover. LIPIcs, Vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pages 86:1-86:13
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::43dbfed9bdcf059a995dfbd20226d325 Zobrazit plný text záznamu