Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

Erschienen in:
Buchtitelbild

Open Access 2021 | OriginalPaper | Buchkapitel

Nondeterministic Syntactic Complexity

verfasst von: Robert S. R. Myers, Stefan Milius, Henning Urbat

Erschienen in: Foundations of Software Science and Computation Structures

Verlag: Springer International Publishing

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.

download
DOWNLOAD
share
TEILEN
print
DRUCKEN
Metadaten
Titel
Nondeterministic Syntactic Complexity
verfasst von
Robert S. R. Myers
Stefan Milius
Henning Urbat
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-71995-1_23

Premium Partner