EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES

DOI10.1142/S0129054103002205MaRDI QIDQ5696956zbMATH OpenFDO

Authors Alexander Okhotin

Publication date 19 October 2005

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054103002205

zbMATH Keywords

cellular automataconjunctive grammarsrecognitionTrellis automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Recommendations

• scientific article; zbMATH DE number 1962778
• scientific article; zbMATH DE number 1948516
• On the equivalence of linear conjunctive grammars and trellis automata
• scientific article; zbMATH DE number 2201371
• A recognition and parsing algorithm for arbitrary conjunctive grammars.

Cites work

• scientific article; zbMATH DE number 5254145 (Why is no real title available?)
• One-way bounded cellular automata

Cited in

(9)

• Space-efficient recognition of sparse self-reducible languages
• Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition
• Conjunctive grammars and alternating pushdown automata
• Language Recognition Power and Succinctness of Affine Automata
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• scientific article; zbMATH DE number 1948516 (Why is no real title available?)
• scientific article; zbMATH DE number 1962778 (Why is no real title available?)
• On the equivalence of linear conjunctive grammars and trellis automata
• Efficient recognition algorithms for boundary and linear eNCE graph languages

This page was built for publication: EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696956)