Amount of nonconstructivity in deterministic finite automata

DOI10.1016/j.tcs.2010.05.038zbMath1206.68155OpenAlexW1974042674MaRDI QIDQ1959651

Rūsiņš Freivalds

Publication date: 7 October 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.038

zbMATH Keywords

Kolmogorov complexityfinite automatanonconstructive methods

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Automata and formal grammars in connection with logical questions (03D05)

Related Items (13)

Hartmanis-Stearns Conjecture on Real Time and Transcendence ⋮ Two-way non-uniform finite automata ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ On the Influence of Technology on Learning Processes ⋮ Determinism and Nondeterminism in Finite Automata with Advice ⋮ Two-Way Non-Uniform Finite Automata ⋮ One-way reversible and quantum finite automata with advice ⋮ On the Amount of Nonconstructivity in Learning Recursive Functions ⋮ Unnamed Item ⋮ On the amount of nonconstructivity in learning formal languages from text ⋮ Quantum State Complexity of Formal Languages ⋮ Advice hierarchies among finite automata ⋮ FINITE AUTOMATA WITH ADVICE TAPES

Cites Work

• Turing machines that take advice
• Polynomial time quantum computation with advice
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• Automata that take advice
• Amount of Nonconstructivity in Finite Automata
• Inductive inference of recursive functions: Complexity bounds
• Non-constructive Methods for Finite Probabilistic Automata
• The definition of random sequences
• Some remarks on the theory of graphs
• SOFSEM 2004: Theory and Practice of Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Amount of nonconstructivity in deterministic finite automata