Publication:3680279

zbMath0565.68046MaRDI QIDQ3680279

Arto Salomaa

Publication date: 1985

zbMATH Keywords

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

68Q25: Analysis of algorithms and problem complexity

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

68Q45: Formal languages and automata

94A60: Cryptography

03-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations

68Q42: Grammars and rewriting systems

68-00: General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science

03-00: General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations

03Dxx: Computability and recursion theory

Related Items

A survey of computational complexity results in systems and control, Multiple splicing systems and the universal computability, Many aspects of formal languages, A deterministic algorithm for modular knapsack problems, On a public-key cryptosystem based on iterated morphisms and substitutions, A D0L-T0L public key cryptosystem, 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, Computability and randomness of Nash equilibrium in infinite games, On number systems with finite degree of ambiguity, Reversibility and surjectivity problems of cellular automata, On recursive bounds for the exceptional values in speed-up, Rice's theorem for the limit sets of cellular automata, A family of NFAs which need 2\(^{n}-\alpha\) deterministic states, Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs, Finite nondeterministic automata: simulation and minimality, Derivation trees of ground term rewriting systems., On the difficulty of making social choices, Hierarchy and equivalence of multi-letter quantum finite automata, Well-structured languages