A Logical Characterization of Small 2NFAs

DOI10.1007/978-3-319-40946-7_14zbMath1379.68225OpenAlexW2502826815MaRDI QIDQ2830217

Lamana Mulaffer, Christos A. 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analogs of Fagin’s Theorem for Small Nondeterministic Finite Automata
• Weak Second‐Order Arithmetic and Finite Automata
• Nondeterministic Space is Closed under Complementation

This page was built for publication: A Logical Characterization of Small 2NFAs