General Algorithms for Testing the Ambiguity of Finite Automata

DOI10.1007/978-3-540-85780-8_8MaRDI QIDQ3533003zbMATH OpenOpenAlexFDO

Authors Cyril Allauzen, Mehryar Mohri, Ashish Rastogi

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_8

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers
• On the degree of ambiguity of finite automata
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• scientific article; zbMATH DE number 4001492
• Probabilistic automata of bounded ambiguity

Cited in

(11)

• scientific article; zbMATH DE number 2081053 (Why is no real title available?)
• Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
• Memoized regular expressions
• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• Queries on XML streams with bounded delay and concurrency
• scientific article; zbMATH DE number 6125212 (Why is no real title available?)
• Bounded Delay and Concurrency for Earliest Query Answering
• Consistently-detecting monitors
• Filters for Efficient Composition of Weighted Finite-State Transducers
• On finite and polynomial ambiguity of weighted tree automata
• General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers

This page was built for publication: General Algorithms for Testing the Ambiguity of Finite Automata

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