scientific article; zbMATH DE number 176733

MaRDI QIDQ4036562zbMATH OpenFDO

Authors Jānis Kaņeps, Rūsiņš Freivalds

Publication date 18 May 1993

zbMATH Keywords

2-dimensional languages2-way probabilistic finite automatalanguage recognitionnonregular languageregular language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• A note on two-way probabilistic automata
• scientific article; zbMATH DE number 1857649
• scientific article; zbMATH DE number 1318511
• Stochasticity of the languages acceptable by two-way finite probabilistic automata

Cited in

(15)

• A note on two-way probabilistic automata
• Automaticity. II: Descriptional complexity in the unary case
• Two-way finite automata with quantum and classical states.
• scientific article; zbMATH DE number 3850478 (Why is no real title available?)
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Reducing Acyclic Cover Transducers
• Stochasticity of the languages acceptable by two-way finite probabilistic automata
• Similarity relations and cover automata
• Probabilistic asynchronous automata
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• A lower bound for probabilistic algorithms for finite state machines
• Minimal cover-automata for finite languages
• Automaticity. IV: Sequences, sets, and diversity
• Streaming word problems
• Characterizations of one-way general quantum finite automata

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036562)