Unrestricted complementation in language equations over a one-letter alphabet

DOI10.1016/0304-3975(94)90227-5zbMath0821.68076OpenAlexW2064508306MaRDI QIDQ1334656

Ernst L. Leiss

Publication date: 25 September 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90227-5

zbMATH Keywords

non-context-free languagescomplete solution systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (24)

Generalized language equations with multiple solutions ⋮ On solving star equations ⋮ Boolean grammars ⋮ Equations over sets of integers with addition only ⋮ Language equations with complementation: decision problems ⋮ On the role of complementation in implicit language equations and relations ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ Implicit language equations: existence and uniqueness of solutions ⋮ Locally stratified Boolean grammars ⋮ Computational completeness of equations over sets of natural numbers ⋮ Decision problems for language equations ⋮ Aspects of shuffle and deletion on trajectories ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ Formal languages over GF(2) ⋮ Least and greatest solutions of equations over sets of integers ⋮ ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS ⋮ On Equations over Sets of Numbers and Their Limitations ⋮ Language equations with complementation: expressive power ⋮ Language equations ⋮ The dual of concatenation ⋮ Regular solutions of language inequalities and well quasi-orders ⋮ Concatenation-free languages ⋮ Unresolved systems of language equations: expressive power and decision problems

Cites Work

• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Generalized language equations with multiple solutions
• On solving star equations
• On generalized language equations
• Language equations over a one-letter alphabet with union, concatenation and star: A complete solution

This page was built for publication: Unrestricted complementation in language equations over a one-letter alphabet