Consensual languages and matching finite-state computations

DOI10.1051/ita/2011012zbMath1219.68112OpenAlexW2121164581MaRDI QIDQ3006160

Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date: 10 June 2011

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2011__45_1_77_0/

zbMATH Keywords

finite automataformal languagescounter machinesParikh mappingconsensual languagesdegree of grammaticalitydescriptive complexity of regular languagesnon-semilinear languagespolynomial time parsing

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Descriptive complexity and finite models (68Q19)

Related Items

Consensual languages and matching finite-state computations ⋮ Counter machines, Petri nets, and consensual computation ⋮ FROM REGULAR TO STRICTLY LOCALLY TESTABLE LANGUAGES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consensual languages and matching finite-state computations
• Consensual Definition of Languages by Regular Sets
• Alternation
• The equivalence of four extensions of context-free grammars