On deterministic finite automata equipped with partial orders

DOI10.1142/S0129054125500388MaRDI QIDQ6854529zbMATH OpenFDO

Authors Jürgen Dassow

Publication date 24 February 2026

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054125500388

zbMATH Keywords

behaviour under operationsdeterministic finite automatamonotonic automataordered automatastate complexity

Mathematics Subject Classification ID

Graph theory (05Cxx) Ordered sets (06Axx) Theory of computing (68Qxx)

Cites work

• A survey on operational state complexity
• scientific article; zbMATH DE number 3473324 (Why is no real title available?)
• Minimal Union-Free Decompositions of Regular Languages
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Nondeterministic tree width of regular languages
• On the number of accepting states of finite automata
• Operational complexity and pumping lemmas
• Operational complexity and right linear grammars
• Provably Shorter Regular Expressions from Deterministic Finite Automata
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Synchronizing monotonic automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Widths of regular and context-free languages

This page was built for publication: On deterministic finite automata equipped with partial orders

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