scientific article; zbMATH DE number 5201369
From MaRDI portal
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
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
cellular automataambiguityfinite automataformal languagesnondeterminismsoftware reliabilitypushdown automatadescriptional complexityparsers
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (36)
State complexity of permutation on finite languages over a binary alphabet ⋮ Complementing two-way finite automata ⋮ 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 ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Improved complement for two-way alternating automata ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ The tractability frontier for NFA minimization ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Existential and universal width of alternating finite automata ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Lower bounds for the transition complexity of NFAs ⋮ Removing nondeterminism in constant height pushdown automata ⋮ 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 ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ Operational state complexity of nested word automata ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ One-Time Nondeterministic Computations ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ State Complexity of Nested Word Automata ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ Size Complexity of Two-Way Finite Automata ⋮ Unambiguity in Automata Theory ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Solving string problems on graphs using the labeled direct product ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Structural properties of NFAs and growth rates of nondeterminism measures
This page was built for publication:
