The dual of concatenation

DOI10.1016/J.TCS.2005.07.019MaRDI QIDQ2575759zbMATH OpenOpenAlexFDO

Authors 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 grammarsSemiringFormal languagesLanguage equationsConjunctive grammarsRegular expressionsCo-context-free languagesDeductive parsing

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

• scientific article; zbMATH DE number 3426894 (Why is no real title available?)
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 2038714 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 941397 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• Boolean grammars
• Conjunctive grammars and systems of language equations
• On the equivalence of linear conjunctive grammars and trellis automata
• Principles and implementation of deductive parsing
• Two Families of Languages Related to ALGOL
• Unresolved systems of language equations: expressive power and decision problems
• Unrestricted complementation in language equations over a one-letter alphabet

Cited in

(18)

• Conditional concatenation
• A simple P-complete problem and its language-theoretic representations
• Formal languages over GF(2)
• An extension of context-free grammars with one-sided context specifications
• scientific article; zbMATH DE number 1916665 (Why is no real title available?)
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Universal first-order quantification over automata
• Language equations with complementation: expressive power
• Language equations with complementation: decision problems
• Recursive descent parsing for Boolean grammars
• On undecidability of the propositional logic of an associative binary modality
• Notes on dual concatenation
• Universal first-order quantification over automata
• Verified decision procedures for MSO on words based on derivatives of regular expressions
• Learning conjunctive grammars and contextual binary feature grammars
• Mathematical Foundations of Computer Science 2004
• The hardest language for conjunctive grammars
• Distributional learning of conjunctive grammars and contextual binary feature grammars

Describes a project that uses

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)