language equation

Ginsburg and Rice{{cite journal|last1=Ginsburg|first1=Seymour|last2=Rice|first2=H. Gordon|title=Two Families of Languages Related to ALGOL|journal=Journal of the ACM|volume=9|issue=3|year=1962|pages=350–371|issn=0004-5411|doi=10.1145/321127.321132|s2cid=16718187|doi-access=free}}

gave an alternative definition of context-free grammars by language equations. To every context-free grammar $G\; =\; (V,\; \backslash Sigma,\; R,\; S)$, is associated a system of equations in variables $V$. Each variable $X\; \backslash in\; V$ is an unknown language over $\backslash Sigma$ and is defined by the equation $X=\backslash alpha\_1\; \backslash cup\; \backslash ldots\; \backslash cup\; \backslash alpha\_m$ where $X\; \backslash to\; \backslash alpha\_1$, ..., $X\; \backslash to\; \backslash alpha\_m$ are all productions for $X$. Ginsburg and Rice used a fixed-point iteration argument to show that a solution always exists, and proved that {{clarify span|the assignment $X=L\_G(X)$ is the least solution to this system,|reason=Indicate what 'L_G(X)' means, in particular, whether it is an expression in the grammar world or in the equations world. I guess, G+R showed that the least solution to the equation system coincides with L(G) in the grammar world.|date=October 2019}} i.e. any other solution must be a {{clarify span|subset|reason=Should probably be 'superset'?|date=October 2019}} of this one.

For example, the grammar

$S\; \backslash to\; a\; S\; c\; \backslash mid\; b\; \backslash mid\; S$

corresponds to the equation system

$S\; =\; (\; \backslash \{\; a\; \backslash \}\; \backslash cdot\; S\; \backslash cdot\; \backslash \{\; c\; \backslash \}\; )\; \backslash cup\; \backslash \{\; b\; \backslash \}\; \backslash cup\; S$

which has as solution every superset of $\backslash \{\; a^n\; b\; c^n\; \backslash mid\; n\; \backslash in\; \backslash mathcal\{N\}\; \backslash \}$.

Language equations with added intersection analogously correspond to conjunctive grammars.{{citation needed|date=October 2019}}

Brzozowski and Leiss{{cite journal|last1=Brzozowski|first1=J.A.|last2=Leiss|first2=E.|title=On equations for regular languages, finite automata, and sequential networks|journal=Theoretical Computer Science|volume=10|issue=1|year=1980|pages=19–35|issn=0304-3975|doi=10.1016/0304-3975(80)90069-9|doi-access=free}} studied left language equations where every concatenation is with a singleton constant language on the left, e.g. $\backslash \{a\backslash \}\; \backslash cdot\; X$ with variable $X$, but not $X\; \backslash cdot\; Y$ nor $X\; \backslash cdot\; \backslash \{a\backslash \}$. Each equation is of the form $X\_i=F(X\_1,\; ...,\; X\_k)$ with one variable on the right-hand side. Every nondeterministic finite automaton has such corresponding equation using left-concatenation and union, see Fig. 1. If intersection operation is allowed, equations correspond to alternating finite automata.

File:DFAexample.svg with associated system of equations $S\_1\; =\; 1\; \backslash cdot\; S\_1\; \backslash cup\; 0\; \backslash cdot\; S\_2\; \backslash cup\; \backslash \{\backslash epsilon\backslash \}$, $S\_2\; =\; 1\; \backslash cdot\; S\_2\; \backslash cup\; 0\; \backslash cdot\; S\_1$ where $\backslash epsilon$ is the empty word.{{rp|21}}]]

Baader and Narendran{{cite journal|last1=Baader|first1=Franz|last2=Narendran|first2=Paliath|title=Unification of Concept Terms in Description Logics|journal=Journal of Symbolic Computation|volume=31|issue=3|year=2001|pages=277–305|issn=0747-7171|doi=10.1006/jsco.2000.0426|doi-access=free}} studied equations $F(X\_1,\; \backslash ldots,\; X\_k)=G(X\_1,\; \backslash ldots,\; X\_k)$ using left-concatenation and union and proved that their satisfiability problem is EXPTIME-complete.

Conway{{cite book | last1=Conway | first1=John Horton | title=Regular Algebra and Finite Machines | publisher=Chapman and Hall | isbn=978-0-486-48583-6 | year=1971}} proposed the following problem: given a constant finite language $L$, is the greatest solution of the equation $LX=XL$ always regular? This problem was studied by Karhumäki and Petre{{cite journal|last1=Karhumäki|first1=Juhani|last2=Petre|first2=Ion|title=Conway's problem for three-word sets|journal=Theoretical Computer Science|volume=289|issue=1|year=2002|pages=705–725|issn=0304-3975|doi=10.1016/S0304-3975(01)00389-9|doi-access=free}}{{cite book|last1=Karhumäki|first1=Juhani|last2=Petre|first2=Ion|title=The Branching Point Approach to Conway's Problem|volume=2300|year=2002|pages=69–76|issn=0302-9743|doi=10.1007/3-540-45711-9_5|series=Lecture Notes in Computer Science|isbn=978-3-540-43190-9}} who gave an affirmative answer in a special case. A strongly negative answer to Conway's problem was given by Kunc{{cite journal|last1=Kunc|first1=Michal|title=The Power of Commuting with Finite Sets of Words|journal=Theory of Computing Systems|volume=40|issue=4|year=2007|pages=521–551|issn=1432-4350|doi=10.1007/s00224-006-1321-z|s2cid=13406797}} who constructed a finite language $L$ such that the greatest solution of this equation is not recursively enumerable.

Kunc{{cite journal|last1=Kunc|first1=Michal|title=Regular solutions of language inequalities and well quasi-orders|journal=Theoretical Computer Science|volume=348|issue=2–3|year=2005|pages=277–293|issn=0304-3975|doi=10.1016/j.tcs.2005.09.018|doi-access=free}} also proved that the greatest solution of inequality $LX\; \backslash subseteq\; XL$ is always regular.

Language equations with concatenation and Boolean operations were first studied by Parikh, Chandra, Halpern and Meyer

{{cite journal|last1=Parikh|first1=Rohit|last2=Chandra|first2=Ashok|last3=Halpern|first3=Joe|last4=Meyer|first4=Albert|title=Equations between Regular Terms and an Application to Process Logic|journal=SIAM Journal on Computing|volume=14|issue=4|year=1985|pages=935–942|issn=0097-5397|doi=10.1137/0214066}} who proved that the satisfiability problem for a given equation is undecidable, and that if a system of language equations has a unique solution, then that solution is recursive. Later, Okhotin{{cite journal|last1=Okhotin|first1=Alexander|title=Decision problems for language equations|journal=Journal of Computer and System Sciences|volume=76|issue=3–4|year=2010|pages=251–266|issn=0022-0000|doi=10.1016/j.jcss.2009.08.002|doi-access=free}} proved that the unsatisfiability problem is RE-complete and that every recursive language is a unique solution of some equation.

For a one-letter alphabet, Leiss{{cite journal|last1=Leiss|first1=E.L.|title=Unrestricted complementation in language equations over a one-letter alphabet|journal=Theoretical Computer Science|volume=132|issue=1–2|year=1994|pages=71–84|issn=0304-3975|doi=10.1016/0304-3975(94)90227-5|doi-access=free}} discovered the first language equation with a nonregular solution, using complementation and concatenation operations. Later, Jeż{{cite journal|last1=Jeż|first1=Artur|title=Conjunctive grammars generate non-regular unary languages|journal=International Journal of Foundations of Computer Science|volume=19|issue=3|year=2008|pages=597–615|issn=0129-0541|doi=10.1142/S012905410800584X}} showed that non-regular unary languages can be defined by language equations with union, intersection and concatenation, equivalent to conjunctive grammars. By this method Jeż and Okhotin{{cite journal|last1=Jeż|first1=Artur|last2=Okhotin|first2=Alexander|title=Computational completeness of equations over sets of natural numbers|journal=Information and Computation|volume=237|year=2014|pages=56–94|issn=0890-5401|doi=10.1016/j.ic.2014.05.001|citeseerx=10.1.1.395.2250}} proved that every recursive unary language is a unique solution of some equation.

• Boolean grammar
• Arden's rule
• Set constraint

{{Reflist}}

• [http://www.math.utu.fi/dlt2007/tale/ Workshop on Theory and Applications of Language Equations (TALE 2007)]

Category:Formal languages

Category:Equations