Difference between revisions of "Publications/fahrenberg.23.pn"
From LRDE
(Created page with "{{Publication | published = true | date = 2023-03-05 | authors = Uli Fahrenberg, Krzysztof Ziemiański | title = A Myhill-Nerode Theorem for Higher-Dimensional Automata | seri...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 13: | Line 13: | ||
| type = inproceedings |
| type = inproceedings |
||
| id = fahrenberg.23.pn |
| id = fahrenberg.23.pn |
||
| + | | identifier = doi:FIXME |
||
| bibtex = |
| bibtex = |
||
@InProceedings<nowiki>{</nowiki> fahrenberg.23.pn, |
@InProceedings<nowiki>{</nowiki> fahrenberg.23.pn, |
||
| Line 23: | Line 24: | ||
(PETRI NETS)<nowiki>}</nowiki>, |
(PETRI NETS)<nowiki>}</nowiki>, |
||
year = <nowiki>{</nowiki>2023<nowiki>}</nowiki>, |
year = <nowiki>{</nowiki>2023<nowiki>}</nowiki>, |
||
| + | doi = <nowiki>{</nowiki>FIXME<nowiki>}</nowiki>, |
||
abstract = <nowiki>{</nowiki>We establish a Myhill-Nerode type theorem for |
abstract = <nowiki>{</nowiki>We establish a Myhill-Nerode type theorem for |
||
higher-dimensional automata (HDAs), stating that a language |
higher-dimensional automata (HDAs), stating that a language |
||
| Line 33: | Line 35: | ||
deterministic HDA. Using our theorem, we develop an |
deterministic HDA. Using our theorem, we develop an |
||
internal characterisation of deterministic languages.<nowiki>}</nowiki>, |
internal characterisation of deterministic languages.<nowiki>}</nowiki>, |
||
| + | month = mar, |
||
note = <nowiki>{</nowiki>Accepted<nowiki>}</nowiki> |
note = <nowiki>{</nowiki>Accepted<nowiki>}</nowiki> |
||
<nowiki>}</nowiki> |
<nowiki>}</nowiki> |
||
Latest revision as of 19:07, 7 April 2023
- Authors
- Uli Fahrenberg, Krzysztof Ziemiański
- Where
- Application and Theory of Petri Nets and Concurrency (PETRI NETS)
- Type
- inproceedings
- Publisher
- Springer
- Projects
- AA"AA" is not in the list (Vaucanson, Spot, URBI, Olena, APMC, Tiger, Climb, Speaker ID, Transformers, Bison, ...) of allowed values for the "Related project" property.
- Date
- 2023-03-05
Abstract
We 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.
Bibtex (lrde.bib)
@InProceedings{ fahrenberg.23.pn,
author = {Fahrenberg, Uli and Ziemia{\'n}ski, Krzysztof},
title = {A {Myhill}-{Nerode} Theorem for Higher-Dimensional
Automata},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
booktitle = {Application and Theory of Petri Nets and Concurrency
(PETRI NETS)},
year = {2023},
doi = {FIXME},
abstract = {We 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.},
month = mar,
note = {Accepted}
}