Acyclic networks maximizing the printing complexity

DOI10.1016/J.TCS.2004.07.006MaRDI QIDQ703493zbMATH OpenOpenAlexFDO

Authors Franck Guingne, Florent Nicart, André Kempe

Publication date 11 January 2005

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

Full work available at URL https://doi.org/10.1016/j.tcs.2004.07.006

zbMATH Keywords

AutomataComplexityTransducersWorst-case

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Running Time Complexity of Printing an Acyclic Automaton
• scientific article; zbMATH DE number 4058887
• Direct construction of minimal acyclic finite states automata
• Minimisation of acyclic deterministic automata in linear time
• An improved algorithm for transitive closure on acyclic digraphs

Cites work

• Characterization of Glushkov automata
• Extraction and recoding of input-\(\varepsilon\)-cycles in finite state transducers.
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1142311 (Why is no real title available?)
• scientific article; zbMATH DE number 2081047 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• The state complexities of some basic operations on regular languages

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Acyclic networks maximizing the printing complexity

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