Publication:5422234
From MaRDI portal
zbMath1258.68058MaRDI QIDQ5422234
Martin Kappes, Andreas Malcher, Jonathan Goldstine, Detlef Wotschke, Chandra M. R. Kintala, Hing-Man Leung
Publication date: 17 October 2007
Full work available at URL: http://www.jucs.org/jucs_8_2/descriptional_complexity_of_machines
cellular automata; ambiguity; finite automata; formal languages; nondeterminism; software reliability; pushdown automata; descriptional complexity; parsers
Related Items
Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals, 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, 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, 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
