A logical characterization of small 2NFAs

DOI10.1007/978-3-319-40946-7_14MaRDI QIDQ2830217zbMATH OpenOpenAlexFDO

Authors Lamana Mulaffer, Christos Kapoutsis

Publication date 9 November 2016

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-40946-7_14

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45)

Recommendations

• A logical characterization of small 2NFAs
• Two-way automata versus logarithmic space
• Two-Way Automata versus Logarithmic Space
• scientific article; zbMATH DE number 408785
• Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata

Cites work

• Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1302020 (Why is no real title available?)
• Minicomplexity
• Nondeterministic Space is Closed under Complementation
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(4)

• A simple combinatorial proof for the small model property of two-variable logic
• Reversal Hierarchies for Small 2DFAs
• scientific article; zbMATH DE number 408785 (Why is no real title available?)
• A logical characterization of small 2NFAs

This page was built for publication: A logical characterization of small 2NFAs

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