Regular languages in \(NC\)
type: Item
instance of: scholarly article
title: Regular languages in \(NC\)
zbMATH Open document ID: 0757.68057
DOI: 10.1016/0022-0000(92)90014-A
author: David A. Mix Barrington
author: Howard Straubing
author: Kevin J. Compton
author: Denis Thérien
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
review text: The paper deals with the problem of recognition of regular languages by the circuits of certain type. The theory of the syntactic monoid of a regular language is used to present various characterizations of the regular languages in the circuit complexity class \(AC^ 0\). Also an effective procedure for deciding the membership of a regular language in \(AC^ 0\) is given, thus answering the decidability question concerning this problem. Variants of the results concerning circuits with gates that compute the sum of the inputs modulo a fixed prime are considered as well.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 58912
zbMATH Keywords: regular languages
zbMATH Keywords: syntactic monoid
zbMATH Keywords: circuit complexity class
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: On uniformity within \(NC^ 1\)
cites work: Finite monoids and the fine structure of NC 1
cites work: Non-uniform automata over groups
cites work: The dot-depth hierarchy of star-free languages is infinite
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Unbounded fan-in circuits and associative functions
cites work: Constant Depth Reducibility
cites work: Q4132170
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Languages that Capture Complexity Classes
cites work: Q3853827
cites work: Q5641083
cites work: Q3769981
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: On finite monoids having only trivial subgroups
cites work: Families of recognizable sets corresponding to certain varieties of finite monoids
cites work: Aperiodic homomorphisms and the concatenation product of recognizable sets
cites work: Q3806849
cites work: CONSTANT-DEPTH PERIODIC CIRCUITS
cites work: Classifying regular events in symbolic logic
cites work: Categories as algebra: An essential ingredient in the theory of monoids
full work available at URL: 0022-0000(92)90014-a
OpenAlex ID: W1972594149
description: scientific article; zbMATH DE number 58912