Detail publikačního výsledku

Controlled Finite Automata

MEDUNA, A.; ZEMEK, P.

Originální název

Controlled Finite Automata

Anglický název

Controlled Finite Automata

Druh

Článek WoS

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

MEDUNA, A.; ZEMEK, P.

Rok RIV

2015

Vydáno

08.07.2014

ISSN

0001-5903

Periodikum

ACTA INFORMATICA

Svazek

51

Číslo

5

Stát

Spolková republika Německo

Strany od

327

Strany do

337

Strany počet

11

URL

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

Plný text v Digitální knihovně

http://hdl.handle.net/

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