Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata

DOI10.1016/0304-3975(91)90277-9MaRDI QIDQ2277854zbMATH OpenOpenAlexFDO

Authors D. Sangiori, Emanuela Fachini, Andrea Maggiolo-Schettini, Giovanni Resta

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90277-9

zbMATH Keywords

closure properties of language classessystolic tree automata

Mathematics Subject Classification ID

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

Review text

This paper continues to investigate systolic tree automata introduced in \textit{K. Culik} II, \textit{J. Gruska}, \textit{A. Salomaa} [Theoretical Computer Science 23, 231-242 (1983; Zbl 0549.68081)]. Since the family of languages recognized by systolic tree automata is not closed under concatenation and Kleene iteration the authors find some restriction on these operations in order to obtain some closure properties of this language family.

Recommendations

• scientific article; zbMATH DE number 4057034
• A Kleene-like characterization of languages accepted by systolic tree automata
• Languages accepted by systolic \(Y\)-tree automata: Structural characterizations
• C-tree systolic automata
• scientific article; zbMATH DE number 3911718

Cites work

• A characterization of systolic binary tree automata and applications
• scientific article; zbMATH DE number 3898246 (Why is no real title available?)
• scientific article; zbMATH DE number 3911718 (Why is no real title available?)
• scientific article; zbMATH DE number 4057034 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 1988977 (Why is no real title available?)
• On a family of L languages resulting from systolic tree automata
• Systolic automata for VLSI on balanced trees

Cited in

(10)

• Languages accepted by systolic \(Y\)-tree automata: Structural characterizations
• A Kleene-like characterization of languages accepted by systolic tree automata
• Systolic tree \(\omega\)-languages: The operational and the logical view
• Systolic tree and tree-like automata
• Systolic automata and P systems
• Closure properties of languages recognized by strictly k-edge finite state automata
• scientific article; zbMATH DE number 4057034 (Why is no real title available?)
• Completeness results concerning systolic tree automata and E0L languages
• On a family of L languages resulting from systolic tree automata
• Synthesis, structure and power of systolic computations

This page was built for publication: Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata

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