Detail publikačního výsledku

Controlled Pure Grammar Systems

MEDUNA, A.; ZEMEK, P.

Originální název

Controlled Pure Grammar Systems

Anglický název

Controlled Pure Grammar Systems

Druh

Článek WoS

Originální abstrakt

This paper discusses grammar systems that have only terminals, work in the leftmost way, and generate their languages under the regulation by control languages over rule labels. It establishes three results concerning their generative power. First, without any control languages, these systems are not even able to generate all context-free languages. Second, with regular control languages, these systems, having no more than two components, characterize the family of recursively enumerable languages. Finally, with control languages that are themselves generated by regular-controlled context-free grammars, these systems over unary alphabets generate nothing but regular languages. In its introductory section, the paper gives a motivation for introducing these systems, and in the concluding section, it formulates several open problems.

Anglický abstrakt

This paper discusses grammar systems that have only terminals, work in the leftmost way, and generate their languages under the regulation by control languages over rule labels. It establishes three results concerning their generative power. First, without any control languages, these systems are not even able to generate all context-free languages. Second, with regular control languages, these systems, having no more than two components, characterize the family of recursively enumerable languages. Finally, with control languages that are themselves generated by regular-controlled context-free grammars, these systems over unary alphabets generate nothing but regular languages. In its introductory section, the paper gives a motivation for introducing these systems, and in the concluding section, it formulates several open problems.

Klíčová slova

formal languages, pure grammar systems, controlled derivations

Klíčová slova v angličtině

formal languages, pure grammar systems, controlled derivations

Autoři

MEDUNA, A.; ZEMEK, P.

Rok RIV

2013

Vydáno

28.10.2012

ISSN

0948-6968

Periodikum

JOURNAL OF UNIVERSAL COMPUTER SCIENCE

Svazek

18

Číslo

14

Stát

Rakouská republika

Strany od

2024

Strany do

2040

Strany počet

17

URL

http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems

BibTex

@article{BUT96924,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Controlled Pure Grammar Systems",
  journal="JOURNAL OF UNIVERSAL COMPUTER SCIENCE",
  year="2012",
  volume="18",
  number="14",
  pages="2024--2040",
  issn="0948-695X",
  url="http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems"
}