The dual of concatenation

DOI10.1016/j.tcs.2005.07.019zbMath1079.68053OpenAlexW2143338666MaRDI QIDQ2575759

Alexander Okhotin

Publication date: 6 December 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.019

zbMATH Keywords

Boolean grammarsSemiringLanguage equationsFormal languagesConjunctive grammarsRegular expressionsCo-context-free languagesDeductive parsing

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Recursive descent parsing for Boolean grammars ⋮ Language equations with complementation: decision problems ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Distributional learning of conjunctive grammars and contextual binary feature grammars ⋮ Universal first-order quantification over automata ⋮ Verified decision procedures for MSO on words based on derivatives of regular expressions ⋮ An extension of context-free grammars with one-sided context specifications ⋮ The Hardest Language for Conjunctive Grammars ⋮ Learning Conjunctive Grammars and Contextual Binary Feature Grammars ⋮ Language equations with complementation: expressive power ⋮ NOTES ON DUAL CONCATENATION

Uses Software

• ALGOL 60

Cites Work

• Unresolved systems of language equations: expressive power and decision problems
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• Boolean grammars
• Principles and implementation of deductive parsing
• On the equivalence of linear conjunctive grammars and trellis automata
• Two Families of Languages Related to ALGOL
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item