The dual of concatenation

DOI10.1016/J.TCS.2005.07.019zbMATH Open1079.68053OpenAlexW2143338666MaRDI QIDQ2575759FDOQ2575759

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

Recommendations

• Mathematical Foundations of Computer Science 2004
• Notes on dual concatenation
• Universal disjunctive concatenation and star
• Formal languages over GF(2)
• scientific article; zbMATH DE number 1916665

zbMATH Keywords

Boolean grammarsSemiringFormal languagesLanguage equationsConjunctive grammarsRegular expressionsCo-context-free languagesDeductive parsing

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unrestricted complementation in language equations over a one-letter alphabet
• Boolean grammars
• Title not available (Why is that?)
• On the equivalence of linear conjunctive grammars and trellis automata
• Two Families of Languages Related to ALGOL
• Unresolved systems of language equations: expressive power and decision problems
• Conjunctive grammars and systems of language equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Principles and implementation of deductive parsing

Cited In (16)

• A simple P-complete problem and its language-theoretic representations
• An extension of context-free grammars with one-sided context specifications
• Title not available (Why is that?)
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Language equations with complementation: expressive power
• Language equations with complementation: decision problems
• On undecidability of the propositional logic of an associative binary modality
• Recursive descent parsing for Boolean grammars
• Universal first-order quantification over automata
• Verified decision procedures for MSO on words based on derivatives of regular expressions
• The Hardest Language for Conjunctive Grammars
• Learning Conjunctive Grammars and Contextual Binary Feature Grammars
• NOTES ON DUAL CONCATENATION
• Mathematical Foundations of Computer Science 2004
• Distributional learning of conjunctive grammars and contextual binary feature grammars
• Conditional concatenation

Uses Software

• ALGOL 60

This page was built for publication: The dual of concatenation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575759)