Publication:5422234

zbMath1258.68058MaRDI QIDQ5422234

Martin Kappes, Detlef Wotschke, Andreas Malcher, Jonathan Goldstine, Hing-Man Leung, Chandra M. R. Kintala

Publication date: 17 October 2007

Full work available at URL: http://www.jucs.org/jucs_8_2/descriptional_complexity_of_machines

zbMATH Keywords

cellular automata; ambiguity; finite automata; formal languages; nondeterminism; software reliability; pushdown automata; descriptional complexity; parsers

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q80: Cellular automata (computational aspects)

Related Items

Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals, One-Time Nondeterministic Computations, Branching Measures and Nearly Acyclic NFAs, Unambiguity in Automata Theory, The State Complexity of Permutations on Finite Languages over Binary Alphabets, Extended regular expressions: succinctness and decidability, Descriptional complexity of bounded context-free languages, Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata, The tractability frontier for NFA minimization, Descriptional complexity of two-way pushdown automata with restricted head reversals, Optimal simulation of self-verifying automata by deterministic automata, Complexity of multi-head finite automata: origins and directions, Lower bounds for the size of deterministic unranked tree automata, Operational state complexity of unary NFAs with finite nondeterminism, Lower bounds for the transition complexity of NFAs, On the descriptional complexity of finite automata with modified acceptance conditions, Succinct representations of languages by DFA with different levels of reliability, On the descriptional power of heads, counters, and pebbles, On two-way communication in cellular automata with a fixed number of cells, Context-free insertion-deletion systems, Complementing unary nondeterministic automata, Removing nondeterminism in constant height pushdown automata, Operational state complexity of nested word automata, State complexity of permutation on finite languages over a binary alphabet, A hitchhiker's guide to descriptional complexity through analytic combinatorics, Complementing two-way finite automata, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, State Complexity of Nested Word Automata, Converting Self-verifying Automata into Deterministic Automata, Size Complexity of Two-Way Finite Automata