From regular to strictly locally testable languages

DOI10.1142/S0129054112400710MaRDI QIDQ2841978zbMATH OpenOpenAlexFDO

Authors Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date 30 July 2013

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

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

zbMATH Keywords

regular languageshomomorphic characterizationfactor decodabilityMedvedev theoremstrictly locally testable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• From regular to strictly locally testable languages
• Regular languages as local functions with small alphabets
• Optimal estimation on the order of local testability of finite automata
• Families of locally testable languages
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES

Cites work

• A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup
• Consensual languages and matching finite-state computations
• Families of locally testable languages
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
• Local languages and the Berry-Sethi algorithm

Cited in

(16)

• Regular languages as local functions with small alphabets
• From regular to strictly locally testable languages
• scientific article; zbMATH DE number 1104369 (Why is no real title available?)
• Reducing local alphabet size in recognizable picture languages
• Two-Sided Strictly Locally Testable Languages
• Strict local testability with consensus equals regularity, and other properties
• Regular languages as images of local functions over small alphabets
• On generalized locally testable languages
• The alphabetic complexity in homomorphic definitions of word, tree and picture languages
• Local testability from words to traces, a suitable definition
• Local variable scoping and Kleene algebra with tests
• Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet
• Right and left strongly locally testable semigroups and languages
• Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
• Homomorphic characterization of tree languages based on comma-free encoding

This page was built for publication: From regular to strictly locally testable languages

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