Nondeterministic Syntactic Complexity

We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns...

Descripción completa

Detalles Bibliográficos
Autores principales: Myers, Robert S. R., Milius, Stefan, Urbat, Henning
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984122/
http://dx.doi.org/10.1007/978-3-030-71995-1_23
_version_ 1783668010021552128
author Myers, Robert S. R.
Milius, Stefan
Urbat, Henning
author_facet Myers, Robert S. R.
Milius, Stefan
Urbat, Henning
author_sort Myers, Robert S. R.
collection PubMed
description We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.
format Online
Article
Text
id pubmed-7984122
institution National Center for Biotechnology Information
language English
publishDate 2021
record_format MEDLINE/PubMed
spelling pubmed-79841222021-03-23 Nondeterministic Syntactic Complexity Myers, Robert S. R. Milius, Stefan Urbat, Henning Foundations of Software Science and Computation Structures Article We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category. 2021-03-23 /pmc/articles/PMC7984122/ http://dx.doi.org/10.1007/978-3-030-71995-1_23 Text en © The Author(s) 2021 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
spellingShingle Article
Myers, Robert S. R.
Milius, Stefan
Urbat, Henning
Nondeterministic Syntactic Complexity
title Nondeterministic Syntactic Complexity
title_full Nondeterministic Syntactic Complexity
title_fullStr Nondeterministic Syntactic Complexity
title_full_unstemmed Nondeterministic Syntactic Complexity
title_short Nondeterministic Syntactic Complexity
title_sort nondeterministic syntactic complexity
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984122/
http://dx.doi.org/10.1007/978-3-030-71995-1_23
work_keys_str_mv AT myersrobertsr nondeterministicsyntacticcomplexity
AT miliusstefan nondeterministicsyntacticcomplexity
AT urbathenning nondeterministicsyntacticcomplexity

Ejemplares similares