Conjunctive grammars, cellular automata and logic

Théo Grente (1) , Etienne Grandjean (1)

1 Equipe AMACC - Laboratoire GREYC - UMR6072

The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-way one-dimensional cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTimeCA: 1) it is true for unary languages; 2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time one-way two-dimensional cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTimeCA and RealTime2OCA.

Mots clés: Computational complexity; Real-time; One-way/two-way communication; Grid-circuit; Unary language; Descriptive complexity; Existential second-order logic; Horn formula

Domaines: Logique en informatique [cs.LO]; Théorie et langage formel [cs.FL]

Théo Grente, Etienne Grandjean. Conjunctive grammars, cellular automata and logic. 2021. ⟨hal-03167529v1⟩