A subclass of deterministic context-free languages with a decidable inclusion problem

DOI10.1007/BF01068604zbMath0800.68530MaRDI QIDQ4007469

P. V. Gorshkov, A. B. Stavrovskij

Publication date: 27 September 1992

Published in: Cybernetics (Search for Journal in Brave)

zbMATH Keywords

free semigroupsdecidabilityfinite automatadirect productdeterministic comtext-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Unnamed Item
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Superdeterministic PDAs
• On the equivalence and containment problems for context-free languages