A note on the space complexity of some decision problems for finite automata

DOI10.1016/S0020-0190(05)80006-7zbMath0741.68078OpenAlexW2031848583MaRDI QIDQ1183428

Tao Jiang, Bala Ravikumar

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(05)80006-7

zbMATH Keywords

computational complexitydecision problempebble automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (19)

Deciding unifiability and computing local unifiers in the description logic \(\mathcal{EL}\) without top constructor ⋮ A note on emptiness for alternating finite automata with a one-letter alphabet ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Similarity in languages and programs ⋮ Decision procedures for inductive Boolean functions based on alternating automata ⋮ Unnamed Item ⋮ Two-way automata and length-preserving homomorphisms ⋮ A note on algebras of languages ⋮ MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON ⋮ Local temporal logic is expressively complete for cograph dependence alphabets ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Succinctness of regular expressions with interleaving, intersection and counting ⋮ COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA ⋮ Unification in the Description Logic $\mathcal{EL}$ without the Top Concept ⋮ Kleene Theorems for Product Systems ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ State complexity of unique rational operations ⋮ On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection ⋮ Note on the complexity of Las Vegas automata problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a complexity hierarchy between L and NL
• Halting space-bounded computations
• Alternation with a pebble
• The parallel complexity of finite-state automata problems
• Space-bounded reducibility among combinatorial problems
• Alternating Pushdown and Stack Automata
• A taxonomy of problems with fast parallel algorithms
• Alternation
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Two-way automata and length-preserving homomorphisms
• State-complexity of finite-state devices, state compressibility and incompressibility
• An Approach to a Unified Theory of Automata

This page was built for publication: A note on the space complexity of some decision problems for finite automata