Publication result detail

Controlled Finite Automata

MEDUNA, A.; ZEMEK, P.

Original Title

Controlled Finite Automata

English Title

Controlled Finite Automata

Type

WoS Article

Original Abstract

This paper discusses finite automata regulated by control languages over their states and transition rules. It proves that under both regulations, regular-controlled finite automata and context-free-controlled finite automata characterize the family of regular languages and the family of context-free languages, respectively. It also establishes conditions under which any state-controlled finite automaton can be turned into an equivalent transition-controlled finite automaton and vice versa. The paper also demonstrates a close relation between these automata and programmed grammars. Indeed, it proves that finite automata controlled by languages generated by propagating programmed grammars with appearance checking are computationally complete. In fact, it demonstrates that this computational completeness holds even in terms of these automata with a reduced number of states.

English abstract

This paper discusses finite automata regulated by control languages over their states and transition rules. It proves that under both regulations, regular-controlled finite automata and context-free-controlled finite automata characterize the family of regular languages and the family of context-free languages, respectively. It also establishes conditions under which any state-controlled finite automaton can be turned into an equivalent transition-controlled finite automaton and vice versa. The paper also demonstrates a close relation between these automata and programmed grammars. Indeed, it proves that finite automata controlled by languages generated by propagating programmed grammars with appearance checking are computationally complete. In fact, it demonstrates that this computational completeness holds even in terms of these automata with a reduced number of states.

Keywords

finite automata, controlled accepting, control languages, accepting power, computational completeness, reduction

Key words in English

finite automata, controlled accepting, control languages, accepting power, computational completeness, reduction

Authors

MEDUNA, A.; ZEMEK, P.

RIV year

2015

Released

08.07.2014

ISBN

0001-5903

Periodical

ACTA INFORMATICA

Volume

51

Number

5

State

Federal Republic of Germany

Pages from

327

Pages to

337

Pages count

11

URL

http://link.springer.com/article/10.1007/s00236-014-0199-5

BibTex

@article{BUT111479,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Controlled Finite Automata",
  journal="ACTA INFORMATICA",
  year="2014",
  volume="51",
  number="5",
  pages="327--337",
  doi="10.1007/s00236-014-0199-5",
  issn="0001-5903",
  url="http://link.springer.com/article/10.1007/s00236-014-0199-5"
}