Languages accepted by systolic \(Y\)-tree automata: Structural characterizations

DOI10.1007/BF01191895zbMath0790.68087MaRDI QIDQ1323359

Emanuela Fachini, Margherita Napoli, Domenico Parente, Angelo Monti

Publication date: 4 July 1994

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

decidability; concatenation; undecidability results; regular sets; systolic systems; \(Y\)-trees; deterministic systolic automata; nondeterministic systolic automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D35: Undecidability and degrees of sets of sentences

68Q80: Cellular automata (computational aspects)

Related Items

Power of interconnections and of nondeterminism in regularY-tree systolic automata, State complexity of SBTA languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a family of L languages resulting from systolic tree automata
• Synthesis, structure and power of systolic computations
• C-tree systolic automata
• Systolic automata for VLSI on balanced trees
• Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata
• Systolic trellis automata: Stability, decidability and complexity
• Systolic trellis automatata †
• SYSTOLIC TREE WITH BASE AUTOMATA
• Power of interconnections and of nondeterminism in regularY-tree systolic automata