scientific article

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity Turing machines cryptography Petri nets computability theory rewriting systems halting problem recursively enumerable sets Hilbert's tenth problem recursive function theory semi-Thue systems degrees of undecidability grammar forms Markov algorithms systolic automata phrase structure grammars Post canonical systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Cryptography (94A60) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Grammars and rewriting systems (68Q42) General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science (68-00) General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations (03-00) Computability and recursion theory (03Dxx)

Related Items

On recursive bounds for the exceptional values in speed-up ⋮ Rice's theorem for the limit sets of cellular automata ⋮ On the difficulty of making social choices ⋮ On a public-key cryptosystem based on iterated morphisms and substitutions ⋮ A D0L-T0L public key cryptosystem ⋮ Well-structured languages ⋮ On a subclass of \(\infty\)-regular languages ⋮ Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors ⋮ Observations concerning a public-key cryptosystem based on iterated morphisms ⋮ The finest homophonic partition and related code concepts ⋮ Characterizing regular languages with polynomial densities ⋮ A family of NFAs which need 2\(^{n}-\alpha\) deterministic states ⋮ ``Viral Turing machines, computation from noise and combinatorial hierarchies ⋮ Bideterministic weighted automata ⋮ Automata methods in transcendence ⋮ Cryptographic protocols for auctions and bargaining ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Products of matrices and recursively enumerable sets ⋮ Computability and randomness of Nash equilibrium in infinite games ⋮ Quasi-universal \(k\)-regular sequences ⋮ On Basic Properties of Jumping Finite Automata ⋮ A survey of computational complexity results in systems and control ⋮ Multiple splicing systems and the universal computability ⋮ Hierarchy and equivalence of multi-letter quantum finite automata ⋮ Unnamed Item ⋮ On number systems with finite degree of ambiguity ⋮ Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs ⋮ Finite transducers and rational transductions ⋮ Finite nondeterministic automata: simulation and minimality ⋮ Languages, Decidability, and Complexity ⋮ Derivation trees of ground term rewriting systems. ⋮ Many aspects of formal languages ⋮ A deterministic algorithm for modular knapsack problems ⋮ Reversibility and surjectivity problems of cellular automata