• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Mirror Images and Schemes for the Maximal Complexity of Nondeterminism

Arto Salomaa, Mirror Images and Schemes for the Maximal Complexity of Nondeterminism. Fundamenta Informaticae 116(1-4), 237–249, 2012.

Abstract:

We present schemes of deterministic finite automata such that, for every nontrivial finite automaton A resulting from the scheme, the state complexity of the reversal of the language of A is maximal. The construction leads to cases, where the increase in state complexity is maximal in the transition from non-deterministic devices to deterministic ones. We also discuss the importance of the size of the alphabet, and present some open problems.

BibTeX entry:

@ARTICLE{jSalomaa_Arto12b,
  title = {Mirror Images and Schemes for the Maximal Complexity of Nondeterminism},
  author = {Salomaa, Arto},
  journal = {Fundamenta Informaticae},
  volume = {116},
  number = {1-4},
  publisher = {IOS Press},
  pages = {237–249},
  year = {2012},
  keywords = {state complexity, finite automata, scheme of automata, nondeterminsm, reversal},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication