On the finite-valuedness problem for sequential machines

DOI10.1016/0304-3975(88)90012-6zbMath0503.68037OpenAlexW2025256949MaRDI QIDQ1173410

Oscar H. Ibarra, Tat-Hung Chan

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90012-6

zbMATH Keywords

space complexityambiguous computations of non-deterministic acceptorssemigroup generated by matrices of nonnegative integers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

A note on finite-valued and finitely ambiguous transducers, On the topological structure of a finitely generated semigroup of matrices, Operations on Unambiguous Finite Automata, FINITELY SUBSEQUENTIAL TRANSDUCERS, On the degree of ambiguity of finite automata, The parallel complexity of finite-state automata problems, GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS, On finitely generated monoids of matrices with entries in $\mathbb {N}$, Branching Measures and Nearly Acyclic NFAs, Operations on Unambiguous Finite Automata, SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS, Deciding path size of nondeterministic (and input-driven) pushdown automata

Cites Work

• On some decision questions concerning pushdown machines
• Relationships between nondeterministic and deterministic tape complexities
• What makes some language theory problems undecidable
• A note on finite-valued and finitely ambiguous transducers