A Logical Characterization of Small 2NFAs

DOI10.1142/S0129054117400019zbMath1380.68254OpenAlexW2771635306MaRDI QIDQ4605508

Lamana Mulaffer, Christos A. Kapoutsis

Publication date: 22 February 2018

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

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

zbMATH Keywords

size complexitynondeterminismtwo-way finite automatadescriptional complexitydescriptive complexityminicomplexity

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