Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

A Myhill-Nerode Theorem for Higher-Dimensional Automata

Uproszczony widok
dc.abstract.enWe establish a Myhill-Nerode type theorem for higher-dimensional automata (HDAs), stating that a language is regular precisely if it has finite prefix quotient. HDAs extend standard automata with additional structure, making it possible to distinguish between interleavings and concurrency. We also introduce deterministic HDAs and show that not all HDAs are determinizable, that is, there exist regular languages that cannot be recognised by a deterministic HDA. Using our theorem, we develop an internal characterisation of deterministic languages.
dc.affiliationUniwersytet Warszawski
dc.conference.countryPortugalia
dc.conference.datefinish2023-06-30
dc.conference.datestart2023-06-25
dc.conference.placeCaparica
dc.conference.seriesInternational Conference on the Application and Theory of Petri Nets and Concurrency (International Conference on the Application and Theory of Petri Nets)
dc.conference.seriesInternational Conference on the Application and Theory of Petri Nets and Concurrency (International Conference on the Application and Theory of Petri Nets)
dc.conference.seriesshortcutPetri Nets (ICAPTN)
dc.conference.shortcutPN 2023
dc.conference.weblinkhttps://petrinets2023.deec.fct.unl.pt
dc.contributor.authorZiemiański, Krzysztof
dc.contributor.authorFahrenberg, Uli
dc.date.accessioned2024-01-24T18:00:18Z
dc.date.available2024-01-24T18:00:18Z
dc.date.issued2023
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1007/978-3-031-33620-1_9
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101691
dc.identifier.weblinkhttps://link.springer.com/chapter/10.1007/978-3-031-33620-1_9
dc.languageeng
dc.pbn.affiliationmathemathics
dc.relation.pages167-188
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enhigher-dimensional automata
dc.subject.enMyhill-Nerode theorem
dc.subject.enconcurrency theory
dc.subject.endeterminism
dc.titleA Myhill-Nerode Theorem for Higher-Dimensional Automata
dc.typeJournalArticle
dspace.entity.typePublication