On the equivalence of linear conjunctive grammars and trellis automata
From MaRDI portal
Publication:4825389
DOI10.1051/ita:2004004zbMath1084.68079OpenAlexW2046935329MaRDI QIDQ4825389
Publication date: 28 October 2004
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2004__38_1_69_0
Algebraic theory of languages and automata (68Q70) Cellular automata (computational aspects) (68Q80) Grammars and rewriting systems (68Q42)
Related Items (32)
Boolean grammars ⋮ Equations over sets of integers with addition only ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Input-driven languages are linear conjunctive ⋮ Deletion along trajectories ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ On hardest languages for one-dimensional cellular automata ⋮ A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Unambiguous Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Computational completeness of equations over sets of natural numbers ⋮ Computing by commuting. ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ On hardest languages for one-dimensional cellular automata ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ BOOLEAN GRAMMARS AND GSM MAPPINGS ⋮ Formal languages over GF(2) ⋮ Least and greatest solutions of equations over sets of integers ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Language equations with complementation: expressive power ⋮ NOTES ON DUAL CONCATENATION ⋮ Language equations ⋮ HOMOMORPHISMS PRESERVING DETERMINISTIC CONTEXT-FREE LANGUAGES ⋮ The dual of concatenation ⋮ Unresolved systems of language equations: expressive power and decision problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On real time one-way cellular array
- On real-time cellular automata and trellis automata
- Characterizations and computational complexity of systolic trellis automata
- Conjunctive grammars and systems of language equations
- On the closure properties of linear conjunctive languages.
- Real-time language recognition by one-dimensional cellular automata
- Systolic trellis automata: Stability, decidability and complexity
- Systolic trellis automatat†
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- One-way bounded cellular automata
This page was built for publication: On the equivalence of linear conjunctive grammars and trellis automata
