A Myhill-Nerode Theorem for Higher-Dimensional Automata

From LRDE

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},
  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}
}