scientific article; zbMATH DE number 2068878

MaRDI QIDQ4465339zbMATH OpenFDO

Authors Andreas Malcher

Publication date 27 May 2004

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Cellular automata (computational aspects) (68Q80)

Recommendations

• Cellular automata: descriptional complexity and decidability
• The size of one-way cellular automata
• Computation theory of cellular automata
• Cellular automata, decidability and phasespace
• Fast reversible language recognition using cellular automata

Cited in

(16)

• On the number of nonterminals in linear conjunctive grammars
• Real-time reversible iterative arrays
• One-way reversible multi-head finite automata
• Cellular Automata with Sparse Communication
• Self-verifying Cellular Automata
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• On two-way communication in cellular automata with a fixed number of cells
• Counter machines and distributed automata -- a story about exchanging space and time
• Cellular automata: descriptional complexity and decidability
• Cellular automata with sparse communication
• On the descriptional power of heads, counters, and pebbles
• The size of one-way cellular automata
• Descriptive complexity for minimal time of cellular automata
• One-way reversible multi-head finite automata
• On the undecidability and descriptional complexity of synchronized regular expressions

This page was built for publication:

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