Myers RS, Milius S, Urbat H (2021)
Publication Type: Conference contribution
Publication year: 2021
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 12650
Pages Range: 448-468
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Online
ISBN: 9783030719944
DOI: 10.1007/978-3-030-71995-1_23
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.
APA:
Myers, R.S., Milius, S., & Urbat, H. (2021). Nondeterministic syntactic complexity. In Stefan Kiefer, Christine Tasson (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 448-468). Online: Springer Science and Business Media Deutschland GmbH.
MLA:
Myers, Robert S.R., Stefan Milius, and Henning Urbat. "Nondeterministic syntactic complexity." Proceedings of the 24th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2021 held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, Online Ed. Stefan Kiefer, Christine Tasson, Springer Science and Business Media Deutschland GmbH, 2021. 448-468.
BibTeX: Download