A proof theory of (omega-)context-free languages, via non-wellfounded proofs
Anupam Das Abhishek De


A non-wellfounded proof theory of (-)context-free languages]A proof theory of (-)context-free languages, 
 via non-wellfounded proofs 

University of Birmingham, UK
{a.das,a.de}@bham.ac.uk



We investigate the proof theory of regular expressions with fixed points, construed as a notation for (ω-)context-free grammars. Starting with a hypersequential system for regular expressions due to Das and Pous <cit.>, we define its extension by least fixed points and prove the soundness and completeness of its non-wellfounded proofs for the standard language model. From here we apply proof-theoretic techniques to recover an infinitary axiomatisation of the resulting equational theory, complete for inclusions of context-free languages. Finally, we extend our syntax by greatest fixed points, now computing ω-context-free languages. We show the soundness and completeness of the corresponding system using a mixture of proof-theoretic and game-theoretic techniques.


[
    Anupam Das Abhishek De
    April 29, 2024
==========================




















theoremTheorem
lemma[theorem]Lemma
proposition[theorem]Proposition
observation[theorem]Observation
observationObservation #2#1#3

corollary[theorem]Corollary
fact[theorem]Fact

definition
definition[theorem]Definition
example[theorem]Example
remark[theorem]Remark




































convention[theorem]Convention


















































































































































































 



§ INTRODUCTION















The characterisation of context-free languages (CFLs) as the least solutions of algebraic inequalities, sometimes known as the ALGOL-like theorem, is a folklore result attributed to several luminaries of formal language theory including Ginsburg and Rice <cit.>, Schutzenberger <cit.>, and Gruska <cit.>.

This induces a syntax for CFLs by adding least fixed point operators to regular expressions, as first noted by Salomaa <cit.>. Leiß <cit.> called these constructs “μ-expressions” and defined an algebraic theory over them by appropriately extending Kleene algebras, which work over regular expressions.




Notable recent developments include a generalisation of Antimirov's partial derivatives to μ-expressions <cit.> and criteria for identifying μ-expressions that can be parsed unambiguously <cit.>.





Establishing axiomatisations and proof systems for classes of formal languages has been a difficult challenge. 
Many theories of regular expressions, such as Kleene algebras () were proposed in the late 20th century (see, e.g., e.g. <cit.>). 
The completeness of  for the (equational) theory of regular languages, due to Kozen <cit.> and Krob <cit.> independently, is a celebrated result that has led to several extensions and refinements, e.g. <cit.>.

More recently the proof theory of  has been studied via infinitary systems. On one hand, <cit.> proposed an ω-branching sequent calculus and on the other hand <cit.> have studied cyclic `hypersequential' calculi. 

Inclusion of CFLs is Π^0_1-complete, so any recursive (hence also cyclic) axiomatisation must necessarily be incomplete. 
Nonetheless various
theories of μ-expressions have been extensively studied, in particular Chomsky algebras and μ-semirings <cit.>, giving rise to a rich algebraic theory. 
Indeed Grathwohl, Henglein, and Kozen <cit.> have  given a complete (but infinitary) axiomatisation of the equational theory of μ-expressions, by extending these algebraic theories with a continuity principle for least fixed points. 






Contributions. In this paper, we propose a non-wellfounded system  for μ-expressions. 
It can be seen as an extension of the cyclic system of <cit.> for regular expressions. 
Our first main contribution is the adequacy of this system for CFLs:  proves e=f just if the CFLs computed by e and f, e and f respectively, are the same. 
We use this result to obtain alternative proof of completeness of the infinitary axiomatisation  of <cit.>, comprising our second main result. 
Our method is inspired by previous techniques in non-wellfounded proof-theory,  namely <cit.>, employing `projections' to translate non-wellfounded proofs to wellfounded ones.
Our result is actually somewhat stronger than that of <cit.>, since our wellfounded proofs are furthermore cut-free.


Finally we develop an extension  of (leftmost)  by adding greatest fixed points, ν, for which · extends to a model of ω-context-free languages. Our third main contribution is the soundness and completeness of  for ·. 
Compared to , the difficulty for metalogical reasoning here is to control interleavings of μ and ν, both for soundness argument and in controlling proof search for completeness.
To this end we employ game theoretic techniques to characterise word membership and control proof search. 







All our main results are summarised in <ref>. 



 §.§ Acknowledgements

This work was supported by a UKRI Future Leaders Fellowship, ‘Structure vs Invariants in Proofs’, project reference MR/S035540/1. The authors are grateful to anonymous reviewers for their helpful comments (in particular, leading to <Ref>) and for pointing us to relevant literature such as <cit.>.  


§ A SYNTAX FOR CONTEXT-FREE GRAMMARS



Throughout this work we make use of a finite set  (the alphabet) of letters, written a,b,…, and a countable set  of variables, written X,Y,….
When speaking about context-free grammars (CFGs), we always assume non-terminals are from  and the terminals are from .


We define (μ-)expressions, written e,f, etc., by:

    e,f,…   
    0 | 
    1  |  X  |  a | 
    e+ f |  e· f |μ X e

We usually simply write ef instead of e· f. μ is considered a variable binder, with the free variables e of an expression e defined as expected:



The set of free variables of an expression e, written e, is defined by:

    
  * 0 ∅
    
  * 1 ∅
    
  * X {X}
    
  * e+f e ∪ f
    
  * ae e
    
  * μ X e e ∖{X}



We sometimes refer to expressions as formulas, and write  for the subformula relation.


μ-expressions compute languages of finite words in the expected way:

    
    Let us temporarily expand the syntax of expressions to include each language A⊆^* as a constant symbol.
We interpret each closed expression (of this expanded language) as a subset of ^* as follows:



.35
    
    
  * 0 ∅
    
  * 1 {ϵ}
    
  * a {a}
    
  * A  A
    
    
    


.6
    
    
    
    
    
    
  * e+f e ∪ f
    
  * ef{ vw : v ∈ e, w ∈ f}
    
  * μ X e(X)⋂{ A ⊇e(A)}




Note that all the operators of our syntax correspond to monotone operations on ^*, with respect to ⊆. Thus μ X e(X) is just the least fixed point of the operation A ↦e(A), by the Knaster-Tarski fixed point theorem.

The productive expressions, written p,q etc. are generated by:

    p,q,…     a   |   p + q   |    p· e   |   e· p   |  μ X p

We say that an expression is guarded if each variable occurrence occurs free in a productive subexpression.
Left-productive and left-guarded are defined in the same way, only omitting the clause e· p in the grammar above.
For convenience of exposition we shall employ the following convention throughout:

    Henceforth we assume all expressions are guarded.




    There are several reasons for employing this convention. 
Most importantly, left-guardedness will be required for our treatment of ω-words later via greatest fixed points, where grammars naturally parse from the left via leftmost derivations. 
In the current setting, over finite words with only least fixed points, it makes little difference whether we use only guarded expressions or not, nor whether we guard from the left or right.
However our convention does simplify some proofs and change some statements; we will comment on such peculiarities when they are important.



[Empty language]

    In the semantics above, note that the empty language ∅ is computed by several expressions, not only 0 but also μ X X and μ X (aX). 
    Note that whle the former is unguarded the latter is (left-)guarded.
    In this sense the inclusion of 0 is somewhat `syntactic sugar', but it will facilitate some of our later development.



    [Kleene star and universal language]
    
    For any expression e we can compute its Kleene star e^* μ X (1 + eX) or e^* μ X (1 + Xe). 
    These definitions are guarded just when e is productive.
     Now, note that we also have not included a symbol ⊤ for the universal language ^*.
     We can compute this by the expression (∑)^*, which is guarded as ∑ is productive.






It is well-known that μ-expressions compute just the context-free (CF) languages <cit.>.
In fact this holds even under the restriction to left-guarded expressions, by simulating the Greibach normal form:


    L is context-free (and ϵ∉ L)  L= e for some e left-guarded (and left-productive, respectively).



While this argument is known, it is pertinent to recall it as we are working with only guarded expressions, and as some of the intermediate concepts will be useful to us later.
First we will need to define a notion of subformula peculiar to fixed point expressions:



The Fischer-Ladner (FL) closure of an expression e, written e, is the smallest set of expressions closed under closed subformulas and, whenever μ X f(X)∈ e then f(μ X f(X))∈ e. 































It is well-known that e is finite, and in fact has size linear in that of e.
Now the  direction of the Adequacy theorem, <ref>, can be proved by construing e as the non-terminals of an appropriate CFG.
Formally, this is broken up into the following two Propositions.



    e is context-free, for any closed expression e.



    We construct a CF grammar with nonterminals X_f for each  f ∈ e, starting nonterminal X_e, and all productions of form:
   
    [             X_1               ϵ;             X_a               a;           X_f+g X_f    |    X_g;            X_fg          X_fX_g;      X_μ X f(X)   X_f(μ X f(X)) ]



For the  direction of <ref>, since we assume only guarded expressions, we work with grammars in Greibach normal form (GNF).
Recall that a GNF grammar is one for which each production has form X → a X⃗ or X→ϵ, for X,X⃗ non-terminals and a∈.
It is well-known that such grammars exhaust all CF languages <cit.>.
Thus we obtain a slightly stronger result:




    L is context-free  L=  e for some left-guarded expression e.
    Moreover if ϵ∉ L then e is left-productive. 


We expand the statement to grammars where each non-terminal has a unique production whose RHS is an arbitrary left-guarded μ-expression, i.e. of the form {X_i → e_i(X⃗)}_i<n for non-terminals X⃗ = X_0, …, X_n-1.
Note that this exhausts all context-free languages by (a) assuming Greibach normal form for left-guardedness; and (b) using + to combine multiple productions from the same non-terminal.
From here we proceed by induction on n, the number of non-terminals, using Bekić's Theorem for resolving equational systems.
Namely from {X_i → e_i(X⃗, X_n)}_i≤ n
we set e_n'(X⃗)μ X_n e_n (X⃗,X_n) and first find solutions f⃗ to the grammar {X_i → e_i(X⃗, e_n' (X⃗))}_i<n, by inductive hypothesis. 
Now we set the solution for X_n to be f_n  e_n'(f⃗).
Note that, since we did not introduce identities, the solutions contain 1 just if there is an ϵ production for some non-terminal, by Greibach normal form.








Consider the left-guarded expressions 1 μ X(1 + ⟨ X ⟩ X) and μ X(1+ a X b).





As suggested, 1 indeed computes the language of well-bracketed words over alphabet {⟨, ⟩},
whereas  computes the set of words a⃗b⃗ with |a⃗| = |b⃗|.


We can also write μ X(1 + aX + Xb), which is guarded but not left-guarded.
However, if we define Kleene * as in <ref>, then we can write a^* and b^* as left-guarded expressions and then take their product for an alternative representation of .

Note that the empty language ∅ is computed by the left-guarded expression μ X (aX), cf. <ref>.
 


§ A NON-WELLFOUNDED PROOF SYSTEM



In this section we extend a calculus  from <cit.> for regular expressions to all μ-expressions, and prove soundness and completeness of its non-wellfounded proofs for the language model ·.
We shall apply this result in the next section to deduce completeness of an infinitary axiomatisation for ·, before considering the extension to greatest fixed points later.










A hypersequent has the form Γ S where Γ (the LHS) is a list of expressions (a cedent) and S (the RHS) is a set of such lists. 

We interpret lists by the product of their elements, and sets by the sum of their elements.
Thus we extend our notation for language semantics by Γ∏Γ and S ⋃_Γ∈ S Γ.











The system  is given by the rules in <ref>.
Here we use commas to delimit elements of a list or set and square brackets [, ] to delimit lists in a set.
In the  rules, we write aS {[a,Γ] : Γ∈ S} and Sa {[Γ,a]:Γ∈ S}.

For each inference step, as typeset in <ref>, the principal formula is the distinguished magenta formula occurrence in the lower sequent, while any distinguished magenta formula occurrences in upper sequents are auxiliary. 
(Other colours may be safely ignored for now).

Our system differs from the original presentation of  in <cit.> as (a) we have general fixed point rules, not just for the Kleene *; and (b) we have included both left and right versions of the  rule, for symmetry. 
We extend the corresponding notions of non-wellfounded proof appropriately:



        A preproof (of ) is generated coinductively from the rules of  i.e. it is a possibly infinite tree of sequents (of height ≤ω) generated by the rules of .
    A preproof is regular or cyclic if it has only finitely many distinct subproofs.
    
    An infinite branch of a preproof is progressing if it has infinitely many μ steps.
    A preproof is progressing, or a ∞-proof, if all its infinite branches are progressing.
    We write Γ S if Γ S has a ∞-proof in , and sometimes write  for the class of ∞-proofs of .


Note that our progress condition on preproofs is equivalent to simply checking that every infinite branch has infinitely many left-logical or  steps, as μ is the only rule among these that does not decrease the size of the LHS.
This is simpler than usual conditions from non-wellfounded proof theory, as we do not have any alternations between the least and greatest fixed points.
Indeed we shall require a more complex criterion later when dealing with ω-languages.
Note that, as regular preproofs may be written naturally as finite graphs, checking progressiveness for them is efficiently decidable (even in , see e.g. <cit.>).

The need for such a complex hypersequential line structure is justified in <cit.> by the desideratum of regular completeness for the theory of regular expressions: intuitionistic `Lambek-like' systems, cf. e.g. <cit.> are incomplete (wrt regular cut-free proofs).
The complexity of the RHS of sequents in  is justified by consideration of proof search for, say, a^*  (aa)^* + a(aa)^* and (a+b)^*  a^*(ba^*)^*, requiring reasoning under sums and products, respectively.









In our extended system we actually gain more regular proofs of inclusions between context-free languages.
For instance:







Recall the guarded expressions  and  from <ref>. 
We have the regular ∞-proof R in <ref> of [],

where ∙ marks roots of identical subproofs. 

Note that indeed the only infinite branch, looping on ∙, has infinitely many μ steps.









































    At this juncture let us make an important point: it is impossible to have any (sound) recursively enumerable system, let alone regular cut-free proofs, complete for context-free inclusions, since this problem is Π^0_1-complete (see e.g. <cit.>).
    In this sense examples of regular proofs are somewhat coincidental.
    





It is not hard to see that each rule of  is sound for language semantics:


For each inference step,

    Γ SΓ_0  S_0⋯Γ_k-1 S_k-1

 for some k≤ 2, we have: ∀ i<k  Γ_i⊆S_iΓ⊆ S.

Consequently finite proofs are also sound, by induction on their structure.
For non-wellfounded proofs, we must employ a less constructive argument, typical of non-wellfounded proof theory:


    
    
        Γ S Γ⊆ S.




For each sequent = Γ S, define n_∈∪{∞} for the least length of word w∈Γ∖ S (if there is no such word then n_ = ∞).
Now suppose, for contradiction, that P is a ∞-proof of = Γ S, but Γ∖ S ≠∅, and so n_∈.
By (the contraposition of) <ref> we may continually choose invalid premisses of rules to build an infinite branch (_i = Γ_i  S_i)_i<ω s.t. Γ_i∖S_i≠∅ for all i<ω.
Moreover, we can guarantee that the sequence (n__i)_i<ω is monotone non-increasing.
For this note that for each inference step _0⋯_k-1 of form as in (<ref>) we have:

    
  *  If  is a  step, then n_ > n__0; and,
    
  * Otherwise there is some i<k with n_ = n__i.

In particular, if  is a + step, we should choose the _i admitting the smallest n__i.
Now, since P is a ∞-proof, (_i)_i<ω must be progressing and has infinitely many μ steps.
We have two cases:

    
  * If (_i)_i<ω has infinitely many  steps then case <ref> happens infinitely often along (n__i)_i<ω, and so it is a monotone non-increasing sequent of natural numbers that does not converge. Contradiction.
    
  * Otherwise (_i)_i≥ k is -step-free, for some k<ω, and so the number of letters in the LHS of the sequent is monotone non-decreasing in i≥ k.
    Since there are infinitely many μ steps, by guardedness the number of producing expressions (whose languages necessarily are nonempty and do not contain ϵ) is strictly increasing, and eventually dominates even n_0≥ n_i. Contradiction. 













By inspection of the rules of  we have:

    
    Let  be a logical step as in (<ref>).
    Γ⊆ S Γ_i⊆S_i, for each i<k.


    
    Γ⊆ S ⇒Γ S.





    
    We describe a bottom-up proof search strategy:
    
        
  *  Apply left logical rules maximally, preserving validity by <ref>.
        Any infinite branch is necessarily progressing.
        
  *  This can only terminate at a sequent of the form a_1, …, a_n  S with a⃗∈ S, whence we mimic a `leftmost' parsing derivation for a⃗ wrt S. 


To flesh out a bit more the <ref> of the argument above, let us state:








    
    a_1⋯ a_n ∈ S ⇒ a_1,…, a_n  S.


    Recall the `canonical' grammar as constructed in (<ref>).
    We proceed by induction on a leftmost (or rightmost) derivation (as defined for Muller CFGs in <ref>) of a⃗ according to this canonical grammar.
 


§ COMPLETENESS OF AN INFINITARY CUT-FREE AXIOMATISATION




While our completeness result above was relatively simple to establish, we can use it, along with proof theoretic techniques, to deduce completeness of an infinitary axiomatisation of the theory of μ-expressions.
In fact we obtain an alternative proof of the result of <cit.>, strengthening it to a `cut-free' calculus . 




Write  for the set of axioms consisting of:

    
  * (0,1,+,·) forms an idempotent semiring (aka a dioid).
    
  * (μ-continuity) eμ X f(X) g = ∑_n<ω ef^n(0)g.
    

We are using the notation f^n(0) defined by f^0(0) 0 and f^n+1(0)  f (f^n(0)).
We also write e≤ f for the natural order given by e + f = f. Now, define  to be the extension of  by the `ω-rule':

    ωΓ , μ X e(X), Γ' S{Γ, e^n(0),Γ' S }_n<ω

By inspection of the rules we have soundness of  for :


    Γ S ∏Γ≤∑_Δ∈ S∏Δ. 

Here the soundness of the ω-rule above is immediate from μ-continuity in .
Note, in particular, that  already proves that μ Xe(X) is indeed a fixed point of e(·), i.e. e(μ Xe(X)) = μ X e(X) <cit.>.


The main result of this section is:


    e f  e≤  f



Note that, immediately from <ref> and <ref>, we obtain:


    e ⊆ f  e≤ f  e≤ f



To prove <ref> we employ similar techniques to those used for an extension of linear logic with least and greatest fixed points <cit.>, only specialised to the current setting.
We only sketch the ideas here, referencing the analogous definitions and theorems from that work at the appropriate moments.





 §.§ Projections

Let us consider cedents Γ = Γ(f_1, …, f_k) where some occurrences of f_1 , … , f_k are distinguished. 
Note that the distinguished occurrences of each f_i may include some, none or all of the occurrences of f_i in Γ, including as subexpressions of of expressions in Γ.
We allow distinct f_i and f_j to be the same formula, as long as they distinguish a disjoint set of occurrences.

When  f⃗ = (μ X_1 g_1(X_1), …, μ X_k g(X_k)) and n⃗∈^k, we write f⃗^n⃗ (g_1^n_1(0), …, g_k^n_k(0)), the list obtained by assigning n⃗ to f⃗.

Let us briefly recap the definition of projectionin <cit.>, specialised to our setting:


    For each  preproof P of Γ(f⃗)  S and n⃗∈^k we define P(n⃗) a preproof of Γ(f⃗^n⃗)  S by coinduction on P:
    
        
  * The definition of P(n⃗) commutes with any step for which a distinguished formula is not principal for a μ step.
        
  * If P ends with a step for which a distinguished formula if μ principal,
        
    μΓ(μ X e(X)), μ X e(X), Γ'(μ X e(X))  SQΓ(μ X e(X)), e(μ X e(X)), Γ'(μ X e(X))  S

        then we proceed by case analysis on the number assigned:
        
    P(0,n⃗)  0Γ(0), 0,Γ'(0)  S

        
    P(n+1,n⃗)0=.45=Γ(e^n+1(0)), e^n+1(0), Γ'(e^n+1(0)) SQ(n,n+1,n⃗)Γ(e^n+1(0)), e(e^n(0)),Γ'(e^n+1(0))  S                0

        where in the second case we have further distinguished the occurrences of μ X e(X) indicated in the auxiliary formula in (<ref>).
        
    



Note that we have technically used a `repetition' rule = in the translation above to ensure productivity of the translation.
However it turns out this is unnecessary, as ∞-proofs are indeed closed under taking projections:



    If P is a  ∞-proof, then so is P(n⃗).


The proof of this result follows the same argument as <cit.>. To briefly recall the idea:

    Each maximal branch B of P(n⃗) is a prefix of some branch B' of P, by inspection of the translation, only with some μ steps replaced by `=' steps or, when B is finite, a 0 step.
    Thus if B is infinite then it must have infinitely many  steps, since B' must be progressing, and so must have infinitely many μ steps too.



In particular we have:


    For each ∞-proof P of Γ, μ X e(X),Γ'  S, P(n) is an ∞-proof of Γ, e^n(0), Γ'  S, for each n < ω.








From here it is simple to provide a translation from  ∞-proofs to  preproofs, as in <ref> shortly.
However, to prove the image of the translation is wellfounded, we shall need some structural proof theoretic machinery, which will also serve later use when dealing with greatest fixed points in <ref>.



 §.§ Intermezzo: ancestry and threads

Given an inference step , as typeset in <ref>, we
say a formula occurrence f in an upper sequent is an immediate ancestor of a formula occurrence e in the lower sequent if they have the same colour; furthermore if e and f are occur in a cedent Γ,Γ',Δ,Δ', they must be the matching occurrences of the same formula (i.e. at the same position in the cedent); similarly if e and f occur in the RHS context S, they must be matching occurrences in matching lists.


Construing immediate ancestry as a directed graph allows us to characterise progress by consideration of its paths:

    
    Fix a preproof P. 
    A thread is a maximal path in the graph of immediate ancestry. 
    An infinite thread on the LHS is progressing if it is infinitely often principal (i.o.p.) for a μ step.





Our overloading of terminology is suggestive:


    P is progressing ⇔ each branch of P has a progressing thread.


    The  direction is trivial.
    For  direction we appeal to König's lemma.
    Fix a branch B and take the subtree of its immediate ancestry graph with nodes the principal formula occurrences along B, and edges given by reachability (`direct ancestry'). 
    By progressiveness this tree is infinite, and by inspection of the rules it is finitely branching, thus it must have an infinite path by König's Lemma. 
    This path induces an infintely often principal thread along B, which in turn must be infinitely often μ principal as every other LHS rule strictly decreases the size of formula.



    Recall the ∞-proof in <ref>. 
    The only infinite branch, looping on ∙, has a progressing thread indicated in magenta.




[See, e.g., <cit.>]

    Any i.o.p. thread has a unique smallest i.o.p. formula, under the subformula relation.
    This formula must be a fixed point formula.






 §.§ Translation to -branching system


We are now ready to give a translation from  to .


    
    For preproofs P define P^ω by coinduction:
    
        
  * ·^ω commutes with any step not a μ.
        
        
  * ( 
        μΓ, μ X e(X) , Γ'  SPΓ, e(μ Xe(X)),Γ'  S    )^ω  ωΓ, μ X e(X),Γ'  S{P(n)^ωΓ, e^n(0),Γ'  S     }_n<ω
    



 <ref> now follows immediately from the following result, obtained by analysis of progressing threads in the image of the ω-translation:


     P is progressing  P^ω is wellfounded.


The proof of <Ref> follows the same argument as for the analogous result in <cit.>.




    Each branch of P^ω can be specified by a branch B of P and a (possibly infinite) sequence of natural numbers n⃗∈ω^≤ω, specifying at each ω-step which premiss to follow. Call this B^n⃗.
    Now, take a progressing thread along B and consider its smallest i.o.p. μ-formula, say μ X e(X).
    If B^n⃗ follows, say the kth premiss at the first corresponding principal step for μ X e(X) in B, write K for height of the (k+1)th unfolding of μ X e(X) in B.
    It follows from inspection of the ω-translation and projections that B^n⃗ has height ≤ K.




    Recalling <ref>, let us see the ω-translation of R in (<ref>).
    First, let us (suggestively) write n for the nth approximant of , i.e. 0  0 and n+1 1 + a  n b. 
    Now R^ω is given below, left, where recursively R(0)  00 and R(n+1) is given below, right:
    
    ω,μ []{ n []    }_n<ω  
        ;
         
            
            
             + 1 + a  n b []1   [ ] 1 ,  11  [1]𝕀 [  ]a n b [  ]·, ·a n  b [  a  ] aa, n  b [  a,  ]μ, +, n  b [    ]·, · n b [   b  ] b n  ,b  [   ,b  ] n

 


§ GREATEST FIXED POINTS AND -LANGUAGES





We extend the grammar of expressions from (<ref>) by:

    e,f …    …  |  ν X e(X)

We call such expressions μν-expressions when we need to distinguish them from ones without ν.
The notions of a (left-)productive and (left-)guarded expression are defined in the same way, extending the grammar of (<ref>) by the clause ν X p.

As expected μν-expressions denote languages of finite and infinite words:


We extend the notation vw to all v,w∈^≤ω by setting vw = v when |v|= ω.

    We extend the definition of · from <ref> to all μν-expressions by setting ν X e(X)⋃{ A ⊆e(A)} where now A varies over subsets of ^≤ω.



Again, since all the operations are monotone, ν X e(X) is indeed the greatest fixed point of the operation A↦e(A), by the Knaster-Tarski theorem.


In fact (ω-)languages computed by μν-expressions are just the `ω-context-free languages' (ω-CFLs), cf. <cit.>, defined as the `Kleene closure' of CFLs:


For A⊆^+ we write A^ω{w_0w_1w_2⋯ : ∀ i<ω  w_i ∈ A}.
The class of ω-CFLs () is defined by:

    := {⋃_i<n A_iB_i^ω :   n<ω ;   A_i,B_i  context-free and ϵ∉ A_i,B_i,  ∀ i<n }
    


It is not hard to see that each ω-CFL is computed by a μν-expression, by noting that e^ω = ν X (eX):


    
    L∈ L =  e for some left-productive e.


Given L=⋃_i=1^n A_iB_i^ω, by <ref> let e_i and f_i be left-productive with e_i=A_i, f_i=B_i for i=1,…, n.
Then, L=∑_i=1^n e_iν X(f_iX).    








We shall address the converse of this result later.
First let us present our system for μν-expressions, a natural extension of  earlier:






    The system  extends  by the rules:

    νΓ, ν X e(X), Γ' SΓ, e(ν X e(X)), Γ' S  νΓ S, [Δ, ν X e(X), Δ']Γ S, [Δ, e(ν X e(X), Δ']


Preproofs for this system are defined just as for  before.

The definitions of immediate ancestor and thread for  extends that of  from <ref> according to the colouring above in (<ref>).


However we must be more nuanced in defining progress, requiring a definition at the level of threads as in <ref>.

Noting that Fact <ref> holds for our extended language with νs as well as μs, we call an i.o.p.  thread a μ-thread (or ν-thread) if its smallest i.o.p. formula is a μ-formula (or ν-formula, respectively).


    Fix a preproof P. 
    We say that an infinite thread τ along a (infinite) branch B of P is progressing if it is i.o.p. and it is a μ-thread on the LHS or it is a ν-thread on the RHS.
    
    
    
    
    
    B is progressing if it has a progressing thread.
    P is a ∞-proof of  if each of its infinite branches has a progressing thread.






Write e ν Z (abZ) and f μ Y(b + ν X (aYX)).
The sequent e [f] has a preproof given in <ref>.
This preproof has just one infinite branch, looping on ∙, which indeed has a progressing thread following the magenta formulas. 
The only fixed point infinitely often principal along this thread is ν X (afX), which is principal at each ∙. Thus this preproof is a proof and e [f] is a theorem of .

Note that, even though this preproof is progressing, the infinite branch's smallest i.o.p. formula on the RHS is not a ν-formula, e.g. given by the magenta thread, as f is also i.o.p. Let us point out that (a) the progressiveness condition only requires existence of a progressing thread, even if other threads are not progressing (like the unique LHS thread above).




 §.§ Some necessary conventions: left-guarded and leftmost

Crucially, due to the asymmetry in the definition of the product of infinite words, we must employ further conventions to ensure soundness and completeness of ∞-proofs for ·.
Our choice of conventions is inspired by the usual `leftmost' semantics of `ω-CFGs', which we shall see in the next section.



First, we shall henceforth work with a lefmost restriction of  in order to maintain soundness for ·:

    A  preproof is leftmost
    if each logical step has principal formula the leftmost formula of its cedent, and there are no -steps.
    Write  for the restriction of  to only leftmost steps and  for the class of ∞-proofs of .


We must also restrict ourselves to left-guarded expressions in the sequel:


Henceforth, all expressions are assumed to be left-guarded.


Let us justify both of these restrictions via some examples.



    Unlike the μ-only setting it turns out that  is unsound without the leftmost restriction, regardless of left-guardedness. 
    For instance consider the preproof,
    
    ν∙ [ν X (aX)]· [aν X(aX)]νa,∙ [a,ν X (aX)]⋮

    where a,∙ roots the same subproof as ∙, but for an extra a on the left of every RHS.
    Of course the endsequent is not valid, as the LHS denotes {ϵ} while the RHS denotes {a^ω}.
    Note also that, while it is progressing thanks to the thread in magenta, it is not leftmost due to the topmost displayed ν step.
























    On the other hand, without the left-guardedness restriction,  is not complete. 
    For instance the sequent ν X X  [ ] , { [a , ν X X]}_a ∈ is indeed valid as both sides compute all of ^≤ω: any word is either empty or begins with a letter.
    However the only available (leftmost) rule application, bottom-up, is ν, which is a fixed point of leftmost proof search, obviously not yielding a progressing preproof.



    





§ METALOGICAL RESULTS: A GAME-THEORETIC APPROACH



Now we return to addressing the expressiveness of both the syntax of μν-expressions and our system , employing game-theoretic methods.



 §.§ Evaluation puzzle and soundness








As an engine for our main metalogical results about , and for a converse to <ref>, we first characterise membership via games:


The evaluation puzzle is a puzzle (i.e. one-player game) whose positions are pairs (w,Γ) where w∈^≤ω and Γ is a cedent, i.e. a list of μν-expressions. A play of the puzzle runs according to the rules in <ref>: puzzle-play is deterministic at each state except when the expression is a sum, in which case a choice must be made. During a play of the evaluation puzzle, formula ancestry and threads are defined as for  preproofs,  by associating each move with the LHS of a left logical rule. 
A play is winning if:

    
  * it terminates at the winning state (ϵ,[ ]); or,
    
  * it is infinite and has a ν-thread (along its right components).




















Define dμ X(⟨⟩ + ⟨ X⟩ X), the set of non-empty well-bracketed words. Let d^ων Y dY. Let us look at a play from (⟨^ω,[d^ω]). 



[cramped, sep=small] 
[r]     (⟨^ω,[d^ω])
[r]     (⟨^ω,[dd^ω])
[r]     (⟨^ω,[d,d^ω])
[r]     (⟨^ω,[⟨⟩+⟨d⟩d,d^ω]) 
[r]     (⟨^ω,[⟨d⟩d,d^ω]) [d]

        …    (⟨^ω,[d,⟩d,d^ω]) [l]     (⟨^ω,[d⟩d,d^ω]) [l]     (⟨^ω,[⟨, d⟩d,d^ω]) [l] 




The play continues without d^ω ever being principal (essentially, going into deeper and deeper nesting to match a ⟨ with a ⟩). Since even the first match is never made, there is no hope of progress. The play (and, in fact, any play) is thus losing. On the other hand, consider the following play from (u,[d^ω]) where u=(⟨⟩)^ω. It is, indeed winning and its ν-thread is indicated in magenta.



[cramped, sep=small] 
[r]     (u,[d^ω])
[r,"_2" near end]     (u,[d,d^ω])
[r]     (u,[⟨⟩+⟨d⟩d,d^ω]) 
[r]     (u,[⟨⟩,d^ω]) 
[r]     (u,[⟨,⟩,d^ω]) 
[r]    (⟩u,[⟩,d^ω]) [lllll,in=-10, out=-170]

































    w ∈Γ ⇔ there is a winning play from (w,Γ).


The proof is rather involved, employing the method of `signatures' common in fixed point logics, cf. e.g. <cit.>, which serve as `least witnesses' to word membership via carefully managing ordinal approximants for fixed points. 
Here we must be somewhat more careful in the argument because positions of our puzzle include cedents, not single formulas: we must crucially assign signatures to each formula of a cedent.
Working with cedents rather than formulas allows the evaluation puzzle to remain strictly single player. This is critical for expressivity: alternating context-free grammars and pushdown automata compute more than just CFLs <cit.>.

The next subsection is devoted to a proof of the Evaluation Theorem above.
Before that, let us give an important consquence:


We can now prove the soundness of  by reduction to <ref>:



Γ S  Γ⊆S. 



Let P be a ∞-proof of Γ S and w∈Γ. We show w∈ S. 

First, since w∈Γ there is a winning play π from (w,Γ) by <ref>, which induces a unique (maximal) branch B_π of P which must have a progressing thread τ.
Now, since π is a winning play from (w,e), τ cannot be on the LHS, so it is an RHS ν-thread following, say, a sequence of cedents [Γ_i]_i<ω.
By construction [Γ_i]_i<ω has an infinite subsequence, namely whenever it is principal, that forms (the right components of) a winning play from (w,Γ_0), with Γ_0 ∈ S. Thus indeed w ∈ S by <ref>.









 §.§ Proof of the Evaluation Theorem

Let us now revisit the argument for <ref> more formally.
This subsection may be safely skipped by the reader comfortable with that result.

Write  for the subformula relation.
Recalling <ref>, let us write e  f if e ∈ f, 
e  f if e f e and e   f if e f  e.


Let the dependency order be ×, i.e. e f if either e f or e f and f  e.


Note that, by the properties of FL closure,  is a well partial order on expressions. In the sequel, we assume an arbitrary extension of  to a total well-order ≤.


Let M and N be finite sets of μ-expressions {μ X_0 e_0  ⋯μ X_n-1 e_n-1} and {ν X_0 e_0  ⋯ν X_n-1 e_n-1} respectively. A μ-signature (respectively, a μ-signature) is a sequence α⃗= (α_i)_i=0^n-1 of ordinals indexed by M (respecively, N). Signatures are ordered by the lexicographical product order.


Let us temporarily expand the language of expressions by,

    e,f, …    …  |  μ^α X e   |  ν^α X e

where α ranges over ordinals.


Fix a finite set of μ-formulas {μ X_0 e_0  ⋯μ X_n-1 e_n-1} and a μ-signature α⃗=(α_i)_i=0^n-1. Given an expression e, its corresponding μ-signed formula e^α⃗ is one where every occurrence μ X_i e_i has been replaced by μ^α_i X_i e_i.


Similarly, given a finite set of ν-formulas, a ν-signature α⃗, and an expression e, its corresponding ν-signed formula e_α⃗ is one where every occurrence of a ν-subformula has been replaced by its corresponding approximant. 

We interpret such expressions by the inflationary and deflationary constructions respectively:

    
  * μ^0 X e(X) ∅
    
  * μ^α +1 X e(X)e(μ^α X e(X))
    
  * μ^λ X e(X)⋃_α <λμ^α X e(X), when λ is a limit ordinal. 
    
  * ν_0 X e(X) ^≤ω
    
  * ν_α +1 X e(X)e(ν^α X e(X))
    
  * ν_λ X e(X)⋂_α <λν^α X e(X), when λ is a limit ordinal. 


Finally, we extend the notion of μ and ν signatures to lists of expressions by writing Γ^α and Γ_α (parameterised by lists of vectors of ordinals now, by abuse of notation) for the corresponding μ and ν-signed lists of Γ. Spelt out, [e_1,…,e_n]^α⃗_1::…::α⃗_n is a shorthand for [e_1^α⃗_1,…,e_n^α⃗_n] (similarly for ν-signed). Lists of vectors are lexicographically ordered.

Recall that least and greatest fixed points can be computed as limits of approximants. 
In particular, we have,

    
  * μ Xe = ⋃_α∈Ordμ^α Xe
    
  * ν Xe = ⋂_α∈Ordν^α Xe

where α ranges over ordinals. Thus we have immediately:


 


Suppose Γ is a list of expressions. We have:

    
  * If w ∈Γ then there is a μ-signature α such that w ∈Γ^α.
    
  * If w∉Γ then there is a ν-signature α such that w ∉Γ_α.









We are now ready to prove our characterisation of evaluation:





    () 
    Suppose w ∈Γ. By <Ref>, there is a least μ-signature α such that w ∈Γ^α. We will construct a winning play (w_i,Γ_i)_i∈λ and sequence of signatures (α^i)_i∈λ from (w,Γ) such that:
    
        
  * (w_0,Γ_0,α⃗_⃗0⃗)=(w,Γ,α);
        
  * for all i∈λ, α^i is a μ-signature such that w_i ∈Γ^α^i;
        
    
where λ∈ω+1. If the play is finite then it is winning by construction, so assume it is infinite i.e. λ=ω.

We will construct it by induction on i. The base case is already defined. For the induction case, assume Γ_i=f,Δ and α_i=α⃗::α and we will do a case -analysis on f.


    
  * Suppose f=f_0+f_1.

    
    w_i ∈[f_0+f_1,Δ]^α⃗::α      [By induction hypothesis]
        w_i∈[f_0+f_1^α⃗,Δ^α]
        w_i∈[f_0^α⃗,Δ^α] or w_i∈[f_1^α⃗,Δ^α]
        w_i∈[f_0,Δ]^α^i or w_i∈[f_1,Δ]^α^i


    Wlog, assume w_i∈[f_0,Δ]^α^i. Choose (w_i+1,Γ_i+1,α^i+1)=(w_i,[f_0,Δ],α_i).

    
    


  * Suppose f=f_0· f_1.

    
    w_i ∈[f_0· f_1,Δ]^α⃗::α      [By induction hypothesis]
        w_i∈[f_0^α⃗,f_1^α⃗,Δ^α]
        w_i∈[f_0,f_1,Δ]^α⃗::α⃗::α

 
 

 Choose (w_i+1,Γ_i+1,α^i+1)=(w_i,[f_0,f_1,Δ],α⃗::α⃗::α).


  * Suppose f=a for some a∈. 

    
    w_i ∈[a,Δ]^α⃗::α      [By induction hypothesis]
        w_i∈[a^α⃗,Δ^α]
        w_i=aw'  and  w'∈Δ^α

 
 

 Choose (w_i+1,Γ_i+1,α^i+1)=(w',Δ,α).


  * Suppose f=ν X f_0.

    
    w_i ∈[ν Xf_0,Δ]^α⃗::α      [By induction hypothesis]
        w_i∈[ν Xf_0^α⃗,Δ^α]
        w_i∈[f_0(ν Xf_0)^α⃗,Δ^α]       [ν X e, Γ=e(ν X e), Γ]
        w_i∈[f_0(ν Xf_0),Δ]^α⃗::α

 

Choose (w_i+1,Γ_i+1,α^i+1)=(w_i,[f_0(ν Xf_0),Δ],α^i)


  * Suppose f=μ X f_0.

    
    w_i ∈[μ Xf_0,Δ]^α⃗::α      [By induction hypothesis]
        w_i∈[μ^α_j Xf_0,Δ^α]       [where α⃗=(α_i)]
        w_i∈[f_0(μ^β Xf_0),Δ^α]       [for some β<α_j]
        w_i∈[f_0(μ Xf_0),Δ]^α⃗'::α       [α⃗'=α⃗[β/α_j]]



Choose (w_i+1,Γ_i+1,α^i+1)=(w_i,[f_0(ν Xf_0),Δ],α⃗'::α) works.

We now claim that this play is winning. Suppose not. Then, the smallest formula principal infinitely often is μ. We follow its thread and obtain a strictly decreasing sequence of ordinals. Contradiction.



() For the converse direction, we will prove the contrapositive. Suppose w∉Γ. Fix an arbitrary play π=(w_i,Γ_i)_i∈λ from (w,Γ) for some λ∈ω+1. By inspection of the puzzle rules, non-membership is preserved i.e. we always have w_i ∉Γ_i. By <ref>, there are ν-signatures α_i such that w_i ∉Γ_α_i. Following an argument like above, the signature corresponding to a thread is a monotone non-increasing sequence. Moreover, if π is winning, it is strictly decreasing. Therefore, π is not winning.





 §.§ -context-freeness via Muller grammars

We can now use the adequacy of the evaluation puzzle to recover a converse of <ref>. For this, we need to recall a grammar-formulation of , due to Cohen and Gold <cit.> and independently Nivat <cit.>.





A Muller (ω-)CFG (MCFG) is a CFG , equipped with a set F⊆ of acceptable sets. 
We define a rewrite relation ⊆ (∪)^* × (∪)^*, leftmost reduction, by
a⃗ X v a⃗ u v
whenever a⃗∈^*, X→ u is a production of G and v ∈ (∪)^*.
A leftmost derivation is just a maximal (possibly infinite) sequence along .
We say
 accepts w ∈^≤ω if there is a leftmost derivation δ such that δ converges to w and the set of infinitely often occurring states that are LHSs of productions along δ is in F.
We write  for the set of words  accepts.




Let L⊆^ω.
L∈⇔ L= G for a MCFG G.










Now we have a converse of <ref> by:


    For each expression e there is a MCFG  s.t. e =.



    Given a μν-expression e, we construct a grammar just like in (<ref>), but with extra clause X_ν X f(X)→ X_f(ν X f(X)). 
    We maintain two copies of each non-terminal, one magenta and one normal, so that a derivation also `guesses' a ν-thread `on the fly'. Formally, the magenta productions of our grammar are:
    
    [                   X_1                     ϵ;                   X_a                     a;                 X_f+g         X_f   |   X_g;                  X_fg X_fX_g    |    X_fX_g;            X_μ X f(X)         X_f(μ X f(X));            X_ν X f(X)         X_f(ν X f(X)) ]

    Productions for normal non-terminals have only normal non-terminals on their RHSs.

    
    Now set F, the set of acceptable sets, to include all sets extending some {X_f : f ∈ E}, for E with smallest expression a ν-formula, by normal non-terminals.
    
    
    Now any accepting leftmost derivation of a word w from X_e describes a winning play of the evaluation puzzle from (w,e) and vice-versa.















 




 §.§ Proof search game and completeness

In order to prove completeness of , we need to introduce a game-theoretic mechanism for organising proof search, in particular so that we can rely on determinacy principles thereof.


    The proof search game (for ) is a two-player game played between Prover (), whose positions are inference steps of , and Denier (), whose positions are sequents of .
A play of the game starts from a particular sequent:
at each turn,  chooses an inference step with the current sequent as conclusion, and  chooses a premiss of that step; the process repeats from this sequent as long as possible.

An infinite play of the game is won by  (aka lost by ) if the branch constructed has a progressing thread; otherwise it is won by  (aka lost by ). In the case of deadlock, the player with no valid move loses.




    
    The proof search game is determined, i.e. from any sequent Γ S, either  or  has a winning strategy.

Note that the winning condition of the proof search game is (lightface) analytic, i.e. Σ^1_1: “there exists a progressing thread”.
Lightface analytic determinacy lies beyond ZFC, as indicated equivalent to the existence of 0# <cit.>.
Further consideration of our metatheory is beyond the scope of this work.





It is not hard to see that -winning-strategies are `just' ∞-proofs.
Our goal is to show a similar result for , a sort of `countermodel construction'.





 has a winning strategy from Γ S  Γ∖ S ≠∅.



Before proving this, let us point out that <ref> applies equally to the system .
We also have the useful observation:

    
     aΓ⊆{ϵ}∪⋃_a∈aS_aΓ⊆S_a.

This follows directly from the definition of ·.
Now we can carry out our `countermodel construction' from -winning-strategies:


Construct a -strategy  that is deadlock-free by always preserving validity, relying on <ref>.
In more detail  does the following:

    
  *  Apply leftmost logical steps (on LHS or RHS) as long as possible.
    
  *  If the LHS is empty and the RHS contains an empty list, then weaken the remainder of the RHS and apply 𝕀.
    
  *  Otherwise, if the LHS has form aΓ and RHS has form aS_a,S, where S contains only lists that are empty or begin with some b≠ a, then apply  and a to obtain the sequent Γ S_a and go back to <ref>.

Now each iteration of <ref> must terminate by left-guardedness and leftmostness.
This must end at a valid sequent, by <ref>,  each of whose lists are either  or begin with a letter, by inspection of the rules.
Now, if the LHS is empty, then the RHS must contain an empty list, and so step <ref> successfully terminates the preproof.
If the LHS has form aΓ, then step <ref> applies and preserves validity by <ref>.

Note that any infinite play of  must repeat step <ref> infinitely often, as each iteration of <ref> terminates, and so has infinitely many  steps and is not ultimately stable.

Now, suppose  is a -winning-strategy and play  against it to construct a play B = (_i)_i<ω = (  Γ_i  S_i)_i<ω. Note that indeed this play must be infinite since (a)  is deadlock-free; and (b)  is -winning.
Now, let w = ∏_ a ∈ B a be the product of labels of  steps along B, in the order they appear bottom-up. We claim w ∈Γ∖ S:

    
  * w ∈Γ. By construction [Γ_i]_i has a subsequence forming an infinite play π of the evaluation puzzle from (w,Γ). 
    Since the play B is won by , B cannot have a μ-thread so it must have a ν-thread (since it is i.o.p.), and so π is winning. Thus w ∈Γ by <ref>.
    
  * w ∉ S. Take an arbitrary play π of the evaluation puzzle from some (w,Δ)  with Δ∈ S.
    This again induces an infinite sequence of cedents [Δ_i]_i<ω along the RHSs of B.
    Now, [Δ_i]_i<ω cannot have a  ν-thread by assumption that B is winning for , and so π is not a winning play of the evaluation puzzle from (w,Δ).
    Since the choices of Δ∈ S and play π were arbitrary, indeed we have w∉ S by <ref>.



Now from <ref>, observing that -winning-strategies are just ∞-proofs, we conclude:


Γ⊆ S Γ S.






§ COMPLEXITY MATTERS AND FURTHER PERSPECTIVES


In this subsection we make further comments, in particular regarding the complexity of our systems, at the level of arithmetical and analytical hierarchies. 
These concepts are well-surveyed in standard textbooks, e.g. <cit.>, as well as various online resources.



Complexity and irregularity for finite words.
The equational theory of μ-expressions in · is actually Π^0_1-complete, i.e. co-recursively-enumerable, due to the same complexity of universality of context-free grammars (see, e.g., <cit.>).
In this sense there is no hope of attaining a finitely presentable (e.g. cyclic, inductive) system for the equational theory of μ-expressions in ·.
However it is not hard to see that our wellfounded system  enjoys optimal Π^0_1 proof search, thanks to invertibility and termination of the rules, along with decidability of membership checking.
Indeed a similar argument is used by Palka in <cit.> for the theory of `*-continuous action lattices'.
Furthermore let us point out that our non-wellfounded system also enjoys optimal proof search: Γ S is equivalent, by invertibility, to checking that every sequent of form a⃗ S reachable by only left rules in bottom-up proof search has a polynomial-size proof (bound induced by length of leftmost derivations).
This is a Π^0_1 property.






Complexity and inaxiomatisability for infinite words.
It would be natural to wonder whether a similar argument to <ref> gives rise to some infinitary axiomatisation of the equational theory of μν-expressions in ·. 
In fact, it turns out this is impossible: the equational theory of ω-CFLs is Π^1_2-complete <cit.>, so there is no hope of a Π^0_1 (or even Σ^1_2) axiomatisation.
In particular, the projection argument of <ref> cannot be scaled to the full system  because · does not distribute over ⋂ in ·, for the corresponding putative `right ω steps' for ν.
For instance 0 = ((aa)^* ∩ a(aa)^*) a^* ≠ (aa)^*a^* ∩ a(aa)^*a^* = aa^*.
Indeed let us point out that here it is crucial to use our hypersequential system  as a base rather than, say, the intuitionistic systems of other proof theoretic works for regular expressions (and friends) <cit.>: the appropriate extension of those systems by μs and νs should indeed enjoy an ω-translation, due to only one formula on the right, rendering them incomplete.

Again let us point out that ∞-provability in , in a sense, enjoys optimal complexity.
By determinacy of the proof search game, Γ S if and only if there is no -winning-strategy from Γ S.
The latter is indeed a Π^1_2 statement: “for every -strategy, there exists a play along which there exists a progressing thread”.



Comparison to <cit.>.
Our method for showing completeness of  is quite different from the analogous result of <cit.> which uses the notion of `rank' for μ-formulas, cf. <cit.>.
Our result is somewhat stronger, giving cut-free completeness, but it could be possible to use ranks directly to obtain such a result too. 
More interestingly, the notion of projections and ω-translation should be well-defined (for LHS μ formulas) even in the presence of νs, cf. <cit.>, whereas the rank method apparently breaks down in such extensions. 
This means that our method should also scale to  ∞-proofs where, say, each infinite branch has a LHS μ-thread.
It would be interesting to see if this method can be used to axiomatise some natural fragments of ω-context-free inclusions.





Note that, strictly speaking, our completeness result for  was only given for the guarded fragment. However it is known that  (and even weaker theories) already proves the equivalence of each expression to one that is even left-guarded, by formalising conversion to Greibach normal form <cit.>.


 


§ CONCLUSIONS

In this work we investigated of the proof theory of context-free languages (CFLs) over a syntax of μ-expressions. 
We defined a non-wellfounded proof system  and showed its soundness and completeness for the model · of context-free languages.

We used this completeness result to recover the same for a cut-free ω-branching system  via proof-theoretic techniques. 
This gave an alternative proof of the completeness for the theory of μ-continuous Chomsky algebras from <cit.>.
We extended μ-expressions by greatest fixed points to obtain a syntax for ω-context-free languages. We studied an extension by greatest fixed points,  and showed its soundness and completeness for the model · of context-free languages, employing game theoretic techniques.



Since inclusion of CFLs is Π^0_1-complete, no recursively enumerable (r.e.) system can be sound and complete for their equational theory. 
However, by restricting products to a letter on the left one can obtain a syntax for right-linear grammars. 
Indeed, for such a restriction complete cyclic systems can be duly obtained <cit.>. 
It would be interesting to investigate systems for related decidable or r.e. inclusion problems, e.g. inclusions of context-free languages in regular languages, and inclusions of visibly pushdown languages <cit.>.




The positions of our evaluation puzzle for μν-expressions use cedents to decompose products, similar to the stack of a pushdown automaton, rather than requiring an additional player. 
Previous works have similarly proposed model-checking games for (fragments/variations of) context-free expressions, cf. <cit.>, where more complex winning conditions seem to be required.
It would be interesting to compare our evaluation puzzle to those games in more detail.


Note
that our completeness result, via determinacy of the proof search game, depends on the assumption of (lightface) analytic determinacy. It is natural to ask whether this is necessary, but this consideration is beyond the scope of this work. 
Let us point out, however, 
that even ω-context-free determinacy exceeds the capacity of ZFC <cit.>.



Finally, it would be interesting to study the structural proof theory arising from systems  and , cf. <cit.>. 
It would also be interesting to see if the restriction to leftmost ∞-proofs can be replaced by stronger progress conditions, such as the `alternating threads' from <cit.>, in a similar hypersequential system for predicate logic.
Note that the same leftmost constraint was employed in <cit.> for an extension of  to ω-regular languages.

 
alpha












