O paralelně komunikujících gramatických systémech a restartovacích automatech zachovávajících správnost

Abstrakt

Článek studuje souvislosti mezi neomezeně přepisujícími restartovacími automaty paralelně komunikujícími gramatickými systémy (PCGS). Zavádějí se pro PCGS dvě míry složitosti.

PCGS, pro které jsou tyto míry omezené kostantou, lze transformovat na speciální restartovací automaty, které provádějí velmi speciální redukční analýzu.

Klíčová slova

• Parallel
• Communicating
• Grammar
• Systems
• Correctness
• Preserving
• Restarting
• Automata