You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Edinburgh » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Edinburgh

Return to search Previous output Next output

Output 43 of 401 in the submission

Output title

Advanced Automata Minimization

Type

E - Conference contribution

DOI

10.1145/2429069.2429079

Name of conference/published proceedings

POPL '13 Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Volume number

Issue number

First page of article

ISSN of proceedings

Year of publication

2013

URL

http://dl.acm.org/citation.cfm?doid=2429069.2429079

Number of additional authors

Additional information

<10> Originality: First paper on general lookahead simulations and general transition pruning techniques for automata minimization and language inclusion checking.

Significance: Minimization of nondeterministic (Buchi) automata and language inclusion checking are computationally hard problems (PSPACE), but important in automata theory and formal verification. This paper led to significantly more efficient practical algorithms which extended the scope of solvable instances by two orders of magnitude. Led to a research hub and software library at www.languageinclusion.org

Rigour: The paper gives a formal description of the methods, correctness proofs, algorithms and an extensive empirical evaluation on many different classes of test cases.

Interdisciplinary

Cross-referral requested

Research group

F - Laboratory for Foundations of Computer Science

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract