Ambiguity and communication

DOI10.1007/S00224-010-9277-4zbMath1246.68146OpenAlexW1970107546MaRDI QIDQ537915

Georg Schnitger, Juraj Hromkovič

Publication date: 23 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1805/

zbMATH Keywords

ambiguitycommunication complexityautomata and formal languagesnondeterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Probabilism versus Alternation for Automata ⋮ Existential and universal width of alternating finite automata ⋮ Operations on Unambiguous Finite Automata ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ Operations on Unambiguous Finite Automata

Cites Work

• On the degree of ambiguity of finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Nondeterministic Communication with a Limited Number of Advice Bits

This page was built for publication: Ambiguity and communication